Find total ways to reach n’th stair with at-most `m` steps
Given a staircase, find the total number of ways to reach the n’th stair from the bottom of the stair when a person is only allowed to take at most m steps at a time.
Tag: Top-down
Find the number of ways to fill an `N × 4` matrix with `1 × 4` tiles
Given an n × 4 matrix where n is a positive number, find the number of ways to fill the matrix with 1 × 4 tiles.
Find total ways to reach the n’th stair from the bottom
Given a staircase, find the total number of ways to reach the n’th stair from the bottom of the stair when a person can only climb either 1 or 2 or 3 stairs at a time.
Weighted Interval Scheduling Problem
Given a list of jobs where each job has a start and finish time, and has profit associated with it, find a maximum profit subset of non-overlapping jobs.
Find total ways to achieve a given sum with `n` throws of dice having `k` faces
Calculate the total number of ways to achieve a given sum with n throws of dice having k faces.
Find ways to calculate a target from elements of the specified array
Write a program to count the number of ways to calculate a target number from the specified array elements using only addition and subtraction operator. The use of any other operator is forbidden.
Count all paths in a matrix from the first cell to the last cell
Given an M × N rectangular grid, efficiently count all paths starting from the first cell (0, 0) to the last cell (M-1, N-1). We can either move down or move towards right from a cell.
Check if a string matches with the given wildcard pattern
Given a string and a pattern containing wildcard characters, write an efficient algorithm to check if the string matches with the wildcard pattern or not.
Pots of Gold Game Problem using Dynamic Programming
There are two players, A & B, in the Pots of the gold game, and pots of gold arranged in a line, each containing some gold coins. The players can see how many coins are there in each gold pot, and each player gets alternating turns in which the player can pick a pot from one of the ends of the line.
Find minimum cuts needed for the palindromic partition of a string
Given a string, find minimum cuts needed to partition it such that each partition is a palindrome.
3–Partition Problem
Given a set S of positive integers, determine if it can be partitioned into three disjoint subsets that all have the same sum, and they cover S.
Total possible solutions to a linear equation of `k` variables
Given a linear equation of k variables, count the total number of possible solutions to it. The problem is similar to finding the total number of ways to get the denomination of coins. Here, coefficients of an equation can be considered coins denominations, and the RHS of an equation can be considered the desired change.