24. Dynamic Programming
1D, grid, knapsack, subsequences, strings, stocks, partition, trees and bitmask DP.
Understand the topic
Dynamic programming is recursion that remembers. When a problem breaks into smaller sub-problems that repeat, solve each one once and store the result: top-down with memoisation, or bottom-up with a table.
Every DP answer needs four things. The state: what does dp[i] (or dp[i][j]) mean in plain words? The transition: how is it built from smaller states? The base cases. And the fill order. Write the state in a comment before you code. The families here are 1D, grid, 0/1 and unbounded knapsack, subsequences (LCS, LIS), strings (edit distance), stock state machines, partition/interval DP, trees and bitmasks.
| # | Problem | Pattern | Level | ||
|---|---|---|---|---|---|
| 1 | Climbing Stairs #70 | 1D DP | Easy | LeetCode ↗ | |
| 2 | Min Cost Climbing Stairs #746 | 1D DP | Easy | LeetCode ↗ | |
| 3 | N-th Tribonacci Number #1137 | 1D DP | Easy | LeetCode ↗ | |
| 4 | House Robber #198 | 1D DP (take / skip) | Medium | LeetCode ↗ | |
| 5 | House Robber II #213 | 1D DP on two ranges | Medium | LeetCode ↗ | |
| 6 | Unique Paths #62 | 2D grid DP | Medium | LeetCode ↗ | |
| 7 | Minimum Path Sum #64 | 2D grid DP | Medium | LeetCode ↗ | |
| 8 | Triangle #120 | Bottom-up DP | Medium | LeetCode ↗ | |
| 9 | Partition Equal Subset Sum #416 | 0/1 knapsack (subset sum) | Medium | LeetCode ↗ | |
| 10 | Target Sum #494 | 0/1 knapsack (count subsets) | Medium | LeetCode ↗ | |
| 11 | Coin Change #322 | Unbounded knapsack (min coins) | Medium | LeetCode ↗ | |
| 12 | Coin Change II #518 | Unbounded knapsack (count combinations) | Medium | LeetCode ↗ | |
| 13 | Longest Common Subsequence #1143 | 2D DP on two strings | Medium | LeetCode ↗ | |
| 14 | Longest Increasing Subsequence #300 | Patience sorting + binary search | Medium | LeetCode ↗ | |
| 15 | Longest Palindromic Subsequence #516 | Interval DP | Medium | LeetCode ↗ | |
| 16 | Edit Distance #72 | 2D DP on two strings | Medium | LeetCode ↗ | |
| 17 | Best Time to Buy and Sell Stock with Cooldown #309 | State machine DP | Medium | LeetCode ↗ | |
| 18 | Best Time to Buy and Sell Stock with Transaction Fee #714 | State machine DP | Medium | LeetCode ↗ | |
| 19 | Word Break #139 | Prefix DP | Medium | LeetCode ↗ | |
| 20 | House Robber III #337 | DP on trees | Medium | LeetCode ↗ | |
| 21 | Beautiful Arrangement #526 | Bitmask DP | Medium | LeetCode ↗ | |
| 22 | Distinct Subsequences #115 | 2D DP counting | Hard | LeetCode ↗ | |
| 23 | Wildcard Matching #44 | 2D DP on string and pattern | Hard | LeetCode ↗ | |
| 24 | Best Time to Buy and Sell Stock III #123 | State machine DP (2 transactions) | Hard | LeetCode ↗ | |
| 25 | Best Time to Buy and Sell Stock IV #188 | State machine DP (k transactions) | Hard | LeetCode ↗ | |
| 26 | Burst Balloons #312 | Interval DP (last to burst) | Hard | LeetCode ↗ | |
| 27 | Minimum Cost to Cut a Stick #1547 | Partition DP (MCM style) | Hard | LeetCode ↗ | |
| 28 | Shortest Path Visiting All Nodes #847 | BFS over (node, visited-mask) | Hard | LeetCode ↗ |
Nothing matches that filter.
Work top to bottom — each list goes from easy to hard. Try a problem for at least 15 minutes before opening a hint. Ticks are saved in your browser.