10 Dynamic Programming Patterns + 50 Problems
By: coding_error1
Pattern 1: 0/1 Knapsack
Core Idea: Include or exclude an item.
dp[i][w] = max(dp[i-1][w], value[i] + dp[i-1][w-weight[i]])
Problems:
1. 0/1 Knapsack
2. Subset Sum
3. Partition Equal Subset Sum
4. Count of Subsets with Given Sum
5. Target Sum (Leetcode 494)
Pattern 2: Unbounded Knapsack
Core Idea: You can reuse items unlimited times.
dp[i][w] = max(dp[i-1][w], dp[i][w-weight[i]] + value[i])
Problems:
6. Coin Change (Minimum Coins)
7. Coin Change 2 (Total Ways)
8. Rod Cutting
9. Maximum Ribbon Cut
10. Combination Sum IV
Pattern 3: Longest Common Subsequence (LCS)
Core Idea: Compare characters and move accordingly.
dp[i][j] = if match → 1 + dp[i-1][j-1] else → max(dp[i-1][j], dp[i][j-
1])
Problems:
11. Longest Common Subsequence
12. Shortest Common Supersequence
13. Delete Operations for Two Strings
14. Longest Palindromic Subsequence
15. Minimum Insertions to Make Palindrome
Pattern 4: Longest Increasing Subsequence (LIS)
Core Idea: Pick elements in increasing order.
dp[i] = max(dp[j] + 1) for all j < i and arr[j] < arr[i]
Problems:
16. Longest Increasing Subsequence
17. Russian Doll Envelopes
18. Box Stacking Problem
19. Maximum Sum Increasing Subsequence
20. Minimum Deletions to Make Array Sorted
Pattern 5: Matrix DP
Core Idea: Fill a 2D grid based on transitions.
Problems:
21. Minimum Path Sum
22. Unique Paths
23. Unique Paths II (with Obstacles)
24. Maximal Square
25. Cherry Pickup
Pattern 6: Partition DP
Core Idea: Try all partitions (cuts).
Problems:
26. Palindrome Partitioning II
27. Burst Balloons
28. Matrix Chain Multiplication
29. Boolean Parenthesization
30. Evaluate Expression to True
Pattern 7: Digit DP
Core Idea: Build numbers digit by digit under constraints.
Problems:
31. Count of Numbers with Unique Digits
32. Numbers with Given Digit Sum
33. Count of Integers with K non-zero digits
34. Count Numbers with Repeated Digits
35. Stepping Numbers in a Range
Pattern 8: Bitmask DP
Core Idea: Use a bitmask to represent visited elements.
Problems:
36. Travelling Salesman Problem
37. Minimum Cost to Connect Cities
38. Assign Tasks (Leetcode 1349)
39. Student Attendance Record
40. Maximum AND Sum of Array
Pattern 9: DP on Subsequences
Core Idea: Include/Exclude style for combinations.
Problems:
41. Count Subsequences with Sum K
42. Distinct Subsequences
43. Interleaving Strings
44. Number of Matching Subsequences
45. Longest Arithmetic Subsequence
Pattern 10: DP on Trees
Core Idea: Solve for child → move up.
Problems:
46. Diameter of Binary Tree
47. Maximum Path Sum in Binary Tree
48. House Robber III
49. Tree DP: Find Largest Subtree Sum
50. Vertex Cover of a Tree
