Dynamic Programming is smart recursion. Instead of solving the same subproblem multiple times, we solve it once and remember the answer. The key insight: if you can express the answer to a problem in terms of answers to smaller problems, DP might work.Analogy: Imagine computing Fibonacci numbers by hand. To get F(50), you need F(49) and F(48). To get F(49), you need F(48) and F(47). Notice F(48) is needed twice—and it explodes from there. Without memoization, computing F(50) requires about 2^50 operations. With memoization (writing each answer on a sticky note the first time you compute it), it takes exactly 50 additions. That is the difference between exponential and linear: DP trades memory for time.
Pattern Recognition Signals:
“Count the number of ways”
“Find minimum/maximum cost”
“Can we achieve X?” (feasibility)
Problem has overlapping subproblems and optimal substructure
Constraints suggest O(n²) or O(n × m) is acceptable
Problem: n stairs, can climb 1 or 2 at a time. Count ways to reach top.State: dp[i] = number of ways to reach stair iTransition: dp[i] = dp[i-1] + dp[i-2] (come from i-1 or i-2)
int climbStairs(int n) { if (n <= 2) return n; vector<int> dp(n + 1); dp[1] = 1; dp[2] = 2; for (int i = 3; i <= n; i++) { dp[i] = dp[i - 1] + dp[i - 2]; } return dp[n];}
int coinChange(vector<int>& coins, int amount) { vector<int> dp(amount + 1, INT_MAX); dp[0] = 0; // Zero coins needed to make amount 0 for (int i = 1; i <= amount; i++) { for (int coin : coins) { // Can we use this coin? (amount >= coin and the remainder is achievable) if (coin <= i && dp[i - coin] != INT_MAX) { dp[i] = min(dp[i], dp[i - coin] + 1); } } } return dp[amount] == INT_MAX ? -1 : dp[amount]; // -1 if amount is unreachable}
Problem: Count ways to make amount (combinations, not permutations).Critical subtlety: The loop order determines whether you count combinations or permutations.
Coins as outer loop (below): Each coin is considered once in order. Result: combinations. and are counted once.
Amount as outer loop: For each amount, try all coins. Result: permutations. , , and are counted separately.
Most problems ask for combinations. Read carefully!
int countWays(vector<int>& coins, int amount) { vector<long long> dp(amount + 1, 0); dp[0] = 1; // One way to make 0: use no coins // Coins as outer loop: counts COMBINATIONS (not permutations) for (int coin : coins) { for (int i = coin; i <= amount; i++) { dp[i] += dp[i - coin]; } } return dp[amount];}// Example: coins = [1, 2, 3], amount = 4// Combinations: {1,1,1,1}, {1,1,2}, {2,2}, {1,3} = 4 ways
Problem: n items with weight and value. Maximize value in capacity W. Each item used at most once.State: dp[i][w] = max value using first i items with capacity wTransition:
Don’t take item i: dp[i][w] = dp[i-1][w]
Take item i: dp[i][w] = dp[i-1][w - weight[i]] + value[i]
int knapsack(vector<int>& weight, vector<int>& value, int W) { int n = weight.size(); vector<vector<int>> dp(n + 1, vector<int>(W + 1, 0)); for (int i = 1; i <= n; i++) { for (int w = 0; w <= W; w++) { dp[i][w] = dp[i - 1][w]; // Don't take if (weight[i - 1] <= w) { dp[i][w] = max(dp[i][w], dp[i - 1][w - weight[i - 1]] + value[i - 1]); } } } return dp[n][W];}// Space optimized: O(W) instead of O(n*W)// Key: iterate capacity BACKWARDS to avoid using same item twiceint knapsack(vector<int>& weight, vector<int>& value, int W) { int n = weight.size(); vector<int> dp(W + 1, 0); for (int i = 0; i < n; i++) { // BACKWARDS: w from W down to weight[i] // This ensures dp[w - weight[i]] still holds the value from // the PREVIOUS item's row (item i not yet taken at that capacity) for (int w = W; w >= weight[i]; w--) { dp[w] = max(dp[w], dp[w - weight[i]] + value[i]); } } return dp[W];}
Why Backwards?: If we iterate forwards, we might use item i multiple times (since dp[w - weight[i]] is already updated). Backwards ensures we use the previous row’s values.
Problem: Find length of longest strictly increasing subsequence.State: dp[i] = length of LIS ending at index iTransition: dp[i] = max(dp[j] + 1) for all j < i where arr[j] < arr[i]
// O(n²) solutionint lis(vector<int>& nums) { int n = nums.size(); vector<int> dp(n, 1); int maxLen = 1; for (int i = 1; i < n; i++) { for (int j = 0; j < i; j++) { if (nums[j] < nums[i]) { dp[i] = max(dp[i], dp[j] + 1); } } maxLen = max(maxLen, dp[i]); } return maxLen;}// O(n log n) solution using binary searchint lisOptimized(vector<int>& nums) { vector<int> tails; // tails[i] = smallest ending element for LIS of length i+1 for (int num : nums) { auto it = lower_bound(tails.begin(), tails.end(), num); if (it == tails.end()) { tails.push_back(num); } else { *it = num; } } return tails.size();}
Key Insight for O(n log n): Maintain the smallest possible tail for each LIS length. Use binary search to find where to place each element.Why this works: tails[i] stores the smallest ending element of all increasing subsequences of length i+1 found so far. This array is always sorted (a longer subsequence must end with a larger value). When a new element arrives, we binary search for where it fits: if it extends the longest subsequence, we append; otherwise, we replace an existing tail with a smaller value, “making room” for future extensions.Walked example: arr = [3, 1, 4, 1, 5, 9, 2, 6]
3: tails = [3]
1: tails = [1] (replace 3—a subsequence of length 1 ending at 1 is better)
Edge case: The tails array does NOT represent an actual LIS—it stores the best tails. To reconstruct the actual subsequence, you need to track parent pointers during the binary search updates.
Rule of Thumb: Start with top-down (easier to write), convert to bottom-up if needed for optimization.
Contest tip: Top-down memoization is usually faster to code and less error-prone (you do not need to figure out loop order). Use it by default. Switch to bottom-up only when you need space optimization (rolling array) or the recursion depth would cause stack overflow.
