Dynamic Programming
Optimisation over overlapping subproblems.
8 pages
- Pattern 14: Dynamic Programming (Memoization vs. Tabulation)Pattern guide
Two skeletons — top-down memo and bottom-up table. Write the recurrence first, in English, before you touch either.
- 0/1 Knapsack ProblemMedium
"Pick or Don't Pick" binary choice for each element. Problem walkthrough from the Dynamic Programming pattern set — Java templates, complexity analysis and…
- LC 198House Robber (LC 198)Medium
"Maximize total, but cannot pick adjacent elements". Problem walkthrough from the Dynamic Programming pattern set — Java templates, complexity analysis and…
- LC 213House Robber II (LC 213) - CircularMedium
"Circular arrangement = solve two linear subproblems". Problem walkthrough from the Dynamic Programming pattern set — Java templates, complexity analysis…
- LC 70Climbing Stairs (LC 70)Easy
Ways to reach step n equals ways to reach n-1 plus ways to reach n-2 (order matters).
- LC 322Coin Change (LC 322)Medium
dp[amount] = minimum coins to make that amount; try every coin as the “last” coin added.
- LC 62Unique Paths (LC 62)Medium
dp[i][j] = dp[i-1][j] + dp[i][j-1] — paths from above + paths from left
- LC 300Longest Increasing Subsequence (LC 300)Medium
dp[i] = LIS length ending at i (O(n²)); or maintain smallest tail values per length (O(n log n)).