Dynamic Programming Master Problem
List (With Patterns)
1. 1D DP
☐ ☐ ☐ ☐ ☐ Fibonacci Numbers - https://leetcode.com/problems/fibonacci-
number/
☐ ☐ ☐ ☐ ☐ Climbing Stairs - https://leetcode.com/problems/climbing-stairs/
☐ ☐ ☐ ☐ ☐ House Robber - https://leetcode.com/problems/house-robber/
☐ ☐ ☐ ☐ ☐ Min Cost Climbing Stairs - https://leetcode.com/problems/min-cost-
climbing-stairs/
☐ ☐ ☐ ☐ ☐ Decode Ways - https://leetcode.com/problems/decode-ways/
☐ ☐ ☐ ☐ ☐ Longest Increasing Subsequence -
https://leetcode.com/problems/longest-increasing-subsequence/
☐ ☐ ☐ ☐ ☐ Paint Fence - https://leetcode.com/problems/paint-fence/
2. 2D DP
☐ ☐ ☐ ☐ ☐ Unique Paths - https://leetcode.com/problems/unique-paths/
☐ ☐ ☐ ☐ ☐ Minimum Path Sum - https://leetcode.com/problems/minimum-path-
sum/
☐ ☐ ☐ ☐ ☐ Longest Common Subsequence -
https://leetcode.com/problems/longest-common-subsequence/
☐ ☐ ☐ ☐ ☐ Edit Distance - https://leetcode.com/problems/edit-distance/
☐ ☐ ☐ ☐ ☐ Longest Palindromic Subsequence -
https://leetcode.com/problems/longest-palindromic-subsequence/
☐ ☐ ☐ ☐ ☐ Interleaving String - https://leetcode.com/problems/interleaving-
string/
3. Knapsack Pattern
☐ ☐ ☐ ☐ ☐ 0/1 Knapsack - https://practice.geeksforgeeks.org/problems/0-1-
knapsack-problem0945/1
☐ ☐ ☐ ☐ ☐ Unbounded Knapsack -
https://practice.geeksforgeeks.org/problems/knapsack-with-duplicate-items4201/1
☐ ☐ ☐ ☐ ☐ Coin Change (number of ways) - https://leetcode.com/problems/coin-
change-2/
☐ ☐ ☐ ☐ ☐ Coin Change (minimum number of coins) -
https://leetcode.com/problems/coin-change/
☐ ☐ ☐ ☐ ☐ Target Sum - https://leetcode.com/problems/target-sum/
☐ ☐ ☐ ☐ ☐ Subset Sum Equal to K - https://www.geeksforgeeks.org/subset-sum-
problem-dp-25/
4. Palindromic Subsequence/Substring Pattern
☐ ☐ ☐ ☐ ☐ Longest Palindromic Substring -
https://leetcode.com/problems/longest-palindromic-substring/
☐ ☐ ☐ ☐ ☐ Palindromic Substrings - https://leetcode.com/problems/palindromic-
substrings/
☐ ☐ ☐ ☐ ☐ Minimum Cuts to Partition a String into Palindromes -
https://leetcode.com/problems/palindrome-partitioning-ii/
☐ ☐ ☐ ☐ ☐ Minimum Insertions to Make a Palindrome -
https://leetcode.com/problems/minimum-insertion-steps-to-make-a-string-
palindrome/
5. Longest Increasing Subsequence (LIS) Pattern
☐ ☐ ☐ ☐ ☐ Longest Increasing Subsequence -
https://leetcode.com/problems/longest-increasing-subsequence/
☐ ☐ ☐ ☐ ☐ Building Bridges - https://www.geeksforgeeks.org/dynamic-
programming-building-bridges/
☐ ☐ ☐ ☐ ☐ Russian Doll Envelopes - https://leetcode.com/problems/russian-doll-
envelopes/
6. Matrix Chain Multiplication Pattern
☐ ☐ ☐ ☐ ☐ Matrix Chain Multiplication - https://www.geeksforgeeks.org/matrix-
chain-multiplication-dp-8/
☐ ☐ ☐ ☐ ☐ Burst Balloons - https://leetcode.com/problems/burst-balloons/
7. Partition DP
☐ ☐ ☐ ☐ ☐ Minimum Cost to Cut a Stick -
https://leetcode.com/problems/minimum-cost-to-cut-a-stick/
☐ ☐ ☐ ☐ ☐ Palindrome Partitioning II -
https://leetcode.com/problems/palindrome-partitioning-ii/
☐ ☐ ☐ ☐ ☐ Evaluate Boolean Expression to True -
https://www.geeksforgeeks.org/boolean-parenthesization-problem-dp-37/
8. Problems on Trees
☐ ☐ ☐ ☐ ☐ Maximum Path Sum in Binary Tree -
https://leetcode.com/problems/binary-tree-maximum-path-sum/
☐ ☐ ☐ ☐ ☐ House Robber III - https://leetcode.com/problems/house-robber-iii/
☐ ☐ ☐ ☐ ☐ Diameter of Binary Tree - https://leetcode.com/problems/diameter-
of-binary-tree/
☐ ☐ ☐ ☐ ☐ Lowest Common Ancestor (with DP optimization) -
https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-tree/
9. Digit DP
☐ ☐ ☐ ☐ ☐ Numbers At Most N Given Digit Set -
https://leetcode.com/problems/numbers-at-most-n-given-digit-set/
☐ ☐ ☐ ☐ ☐ Count Numbers with Unique Digits -
https://leetcode.com/problems/count-numbers-with-unique-digits/
☐ ☐ ☐ ☐ ☐ Prime Number of Set Bits - https://leetcode.com/problems/prime-
number-of-set-bits-in-binary-representation/
10. Bitmasking DP
☐ ☐ ☐ ☐ ☐ Traveling Salesperson Problem (TSP) -
https://www.geeksforgeeks.org/solve-dynamic-programming-problem-tsp/
☐ ☐ ☐ ☐ ☐ Minimum Cost to Visit Every Node in a Graph -
https://leetcode.com/problems/minimum-cost-to-visit-every-node/
☐ ☐ ☐ ☐ ☐ Maximum XOR Subset - https://www.geeksforgeeks.org/find-
maximum-xor-subset-given-set/
