Mastering Dynamic Programming: The 6-Step Framework with Examples

Dynamic Programming (DP) is often perceived as the most intimidating topic in coding interviews. However, DP is not magic — it is simply an optimization over brute-force recursion where overlapping computations are cached.

---

The 6-Step Dynamic Programming Framework

Whenever you encounter an optimization problem (Min/Max, Total Count, Boolean Possibility), apply these 6 steps:

1. Define the State: What variables uniquely describe a subproblem? (e.g., dp[i] = min cost to reach step i).
2. Formulate the Recurrence Relation: How does the answer for state i relate to smaller subproblems? (e.g., dp[i] = min(dp[i-1], dp[i-2]) + cost[i]).
3. Identify Base Cases: What are the smallest trivial subproblems you can solve directly? (e.g., dp[0] = 0, dp[1] = 1).
4. Determine Order of Computation: Should you compute iteratively bottom-up (tabulation) or top-down (memoization)?
5. Implement and Test: Write clean code and verify with small inputs on paper.
6. Space Optimization: Can you store only the last 1-2 states instead of an entire array?

---

Classic Case Study: 0/1 Knapsack Problem

Problem Statement:

Given weights wt[] and values val[] of N items, find the maximum value that can be put in a knapsack of capacity W.

Recurrence Relation:

For each item i with remaining capacity w:

• If we exclude item i: dp[i][w] = dp[i-1][w]
• If we include item i (only if wt[i-1] <= w): dp[i][w] = max(dp[i-1][w], val[i-1] + dp[i-1][w - wt[i-1]])

int knapSack(int W, const vector<int>& wt, const vector<int>& val, int n) {
    vector<vector<int>> dp(n + 1, vector<int>(W + 1, 0));

    for (int i = 1; i <= n; i++) {
        for (int w = 1; w <= W; w++) {
            if (wt[i - 1] <= w) {
                dp[i][w] = max(val[i - 1] + dp[i - 1][w - wt[i - 1]], dp[i - 1][w]);
            } else {
                dp[i][w] = dp[i - 1][w];
            }
        }
    }
    return dp[n][W];
}

---

Top 5 DP Patterns to Master

1. 0/1 Knapsack & Unbounded Knapsack (Coin Change, Partition Equal Subset Sum).
2. Longest Common Subsequence (LCS) (Edit Distance, Shortest Common Supersequence).
3. Longest Increasing Subsequence (LIS) (Russian Doll Envelopes).
4. Matrix Chain Multiplication / Interval DP (Burst Balloons).
5. State Machine / Buy & Sell Stocks (Stock transactions with cool-down / fee).