- Fibonacci nos
- Climbing stairs | Count distinct sol
- Frog Jump | Min Energy to climb height
- House Robber | Maximum sum of non-adjacent els or Max sum of subseq
- House Robber 2 | Maximum sum of non-adjacent els in CIRCULAR array
- Ninja Training | N days, 3 tasks, calc max points
DP on Grids/2D matrices
- Count Grid Unique Paths | all paths are unique in rec | down and right
- Unique Paths II
- Minimum Path Sum | Each cell has a cost
DP on Subsequences/Subsets and target
- Subset sum equal to K | Check if problem
- Count Subsets having sum == K | Positive nums
- Partition Equal Subset Sum | Check if array can be partitioned into two equal subsets having same sum
- Partition Array Into Two Arrays to Minimize Sum Difference | Find min abs diff
- Count no of Partitions with given difference
- Target Sum | variation of prev question
- Permutation Sum | count subset permutation == k
Classic Problems
- 0/1 Knapsack
- Coin Change I, min coins | Coin denomination and target problem
- Coin Change II | number of combinations that make up that amount
- Unbounded Knapsack | picking an item multiple times
- Rod Cutting Problem | lens associated cost, return max cost
DP on strings
- Length of Longest Common Subsequence(LCS)
- Length of Longest Common Substring(Without Tabulation sol)
- Len of Longest Palindromic Subsequence | LCS b/w str and rev of str
- Len of Longest Repeating Subsequence | LCS b/w str and str but both indices should be different
- Number of times the second string occurs in the first string | No-LCS involved
DP on stocks: Best time to buy and sell stocks
- Max profit on stock | Buy/Sell only once
- Max profit on stock | Buy/Sell any no of times
- Max profit on stock | Buy/Sell at only two time
- Max profit on stock | Buy/Sell at most k times
- Max profit on stock | Cannot Buy after sell immediately but infinite buy/sell
- Max profit on stock | Trasaction Fee but infinite buy/sell
DP on LIS
- Len of Longest Increasing Subsequence(LIS) using DP
- Len of Longest Increasing Subsequence(LIS) using Binary Search | O(nlogn) time
- Minimum Deletions to make array sorted
- Maximum sum increasing subsequence
- Longest Bitonic subsequence
- Longest chain of pairs
Misc
How do you know it's a DP problem?
- counting no of ways
- minimum or maximum op in case of multiple ways
- whenever concept of try all possible ways
Tips for developing recurrence relation
- try to represent the problem in terms of index
- do all possible stuffs on that index according to PS
- if question says count all ways:
- sum up all stuffs
- else if question says find min
- take min(all stuffs)