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.
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)
Copy
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];}
Problem: Given coins, find minimum coins to make amount.State: dp[i] = minimum coins to make amount iTransition: dp[i] = min(dp[i - coin] + 1) for each coin
Copy
int coinChange(vector<int>& coins, int amount) { vector<int> dp(amount + 1, INT_MAX); dp[0] = 0; for (int i = 1; i <= amount; i++) { for (int coin : coins) { 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];}
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]
Copy
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 (iterate backwards!)int 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++) { for (int w = W; w >= weight[i]; w--) { // Backwards! 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]
Copy
// 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.Codeforces Problems:
