Dynamic Programming Core: One Framework for 5 Problems (LC 70/198/322/300/1143)

Many people think DP is the "flash of insight" type — it's actually the opposite. DP is the most formulaic topic, and the formula is these five steps:

① Define the state (what is dp[i]) → ② Write the transition (how dp[i] comes from smaller subproblems) → ③ Base cases → ④ Compute order → ⑤ Where the answer is

Fill in those five and the code almost grows itself. The hard part is never the loop — it's "what does dp[i] actually mean." Get the state right and the transition surfaces naturally.

This post drills the framework into reflex across 5 problems, continuing the full derivation flow:

📋 Problem → 🧭 break down → brute force → bottleneck → insight → optimum → code

• Linear recurrence (70 climbing stairs) → recurrence with a choice (198 house robber) → optimization to make a total (322 coin change) → subsequence DP (300 LIS, 1143 LCS)

① LC 70 — Climbing Stairs

📋 Problem: Climbing n stairs, each step you can climb 1 or 2 steps; how many distinct ways to reach the top?

Example: n = 2 → 2 (1+1, 2); n = 3 → 3 (1+1+1, 1+2, 2+1)

🧭 From reading the problem to the solution

1. Break it down: to reach step n, the last move is either +1 from n-1 or +2 from n-2. So ways(n) = ways(n-1) + ways(n-2).
2. Apply the framework:
   • State: dp[i] = number of ways to reach step i.
   • Transition: dp[i] = dp[i-1] + dp[i-2] (Fibonacci).
   • Base: dp[1] = 1, dp[2] = 2.
   • Order: i ascending. Answer: dp[n].
3. Optimum: keep only the last two values in two rolling variables, O(1) space.

def climbStairs(n):
    if n <= 2:
        return n
    a, b = 1, 2                    # ways to reach step 1, step 2
    for _ in range(3, n + 1):
        a, b = b, a + b            # roll forward
    return b

int climbStairs(int n) {
    if (n <= 2) return n;
    int a = 1, b = 2;
    for (int i = 3; i <= n; i++) {
        int c = a + b;
        a = b; b = c;
    }
    return b;
}

• Complexity: O(n) time, O(1) space.
• Pitfall: ① it's Fibonacci — recognize it and it's instant; ② rolling variables drop the whole dp array; ③ think "where did the last step come from" — the opening move of all linear DP.

② LC 198 — House Robber

📋 Problem: Houses in a row with amounts nums[i]; you can't rob two adjacent houses (triggers an alarm). Return the max amount you can rob.

Example: nums = [1,2,3,1] → 4 (rob 1+3); [2,7,9,3,1] → 12 (rob 2+9+1)

🧭 From reading the problem to the solution

1. Break it down: at house i you face a binary choice: rob it (then not i-1, total = dp[i-2] + nums[i]) or skip it (total = dp[i-1]). Take the larger.
2. Apply the framework:
   • State: dp[i] = max amount considering the first i houses.
   • Transition: dp[i] = max(dp[i-1], dp[i-2] + nums[i]) (skip vs rob).
   • Base: dp[0] = nums[0], dp[1] = max(nums[0], nums[1]).
   • Answer: dp[n-1].
3. Key insight: DP's essence is "make the optimal choice at each state" — this "rob/skip" is the classic choice transition.
4. Optimum: two rolling variables.

def rob(nums):
    prev, curr = 0, 0              # best up to i-2, up to i-1
    for n in nums:
        prev, curr = curr, max(curr, prev + n)   # skip vs rob
    return curr

int rob(vector<int>& nums) {
    int prev = 0, curr = 0;
    for (int n : nums) {
        int next = max(curr, prev + n);   // skip vs rob
        prev = curr; curr = next;
    }
    return curr;
}

• Complexity: O(n) time, O(1) space.
• Pitfall: ① the transition is "skip (inherit dp[i-1]) vs rob (dp[i-2]+nums[i])" — don't drop the "skip" branch; ② initializing prev/curr both to 0 is clean; ③ the harder LC 213 (circular) is just two linear DPs splitting first/last.

③ LC 322 — Coin Change

📋 Problem: Given coin denominations coins (each usable unlimited times) and a target amount, return the fewest coins to make amount, or -1 if impossible.

Example: coins = [1,2,5], amount = 11 → 3 (5+5+1); coins = [2], amount = 3 → -1

🧭 From reading the problem to the solution

1. Break it down: to make amount, if the last coin is coin, the rest is "fewest coins to make amount - coin" + 1. Try every coin, take the min.
2. The wrong instinct: greedily "take the biggest coin each time" — counterexample: coins=[1,3,4], amount=6, greedy gives 4+1+1=3 coins, but optimal is 3+3=2. Greedy fails for arbitrary denominations — use DP.
3. Apply the framework:
   • State: dp[a] = fewest coins to make amount a.
   • Transition: dp[a] = min(dp[a - coin] + 1) over all coin <= a.
   • Base: dp[0] = 0.
   • Answer: dp[amount], or -1 if still infinite.
4. Optimum: fill the dp array bottom-up.

def coinChange(coins, amount):
    dp = [float('inf')] * (amount + 1)
    dp[0] = 0
    for a in range(1, amount + 1):
        for coin in coins:
            if coin <= a:
                dp[a] = min(dp[a], dp[a - coin] + 1)
    return dp[amount] if dp[amount] != float('inf') else -1

int coinChange(vector<int>& coins, int amount) {
    vector<int> dp(amount + 1, amount + 1);   // amount+1 as "infinity"
    dp[0] = 0;
    for (int a = 1; a <= amount; a++)
        for (int coin : coins)
            if (coin <= a)
                dp[a] = min(dp[a], dp[a - coin] + 1);
    return dp[amount] > amount ? -1 : dp[amount];
}

• Complexity: O(amount × len(coins)) time, O(amount) space.
• Pitfall: ① don't use greedy (arbitrary denominations break it); ② initialize with "infinity" (use amount+1 as a sentinel in C++ to avoid overflow), then check if it's still infinite for -1; ③ this is the "unbounded knapsack, minimize" template — recognize it and a whole class falls.

④ LC 300 — Longest Increasing Subsequence

📋 Problem: Given an integer array nums, return the length of the longest strictly increasing subsequence (not necessarily contiguous).

Example: [10,9,2,5,3,7,101,18] → 4 (2,3,7,101); [0,1,0,3,2,3] → 4

🧭 From reading the problem to the solution

1. Break it down: subsequence, longest — classic DP. The trick is defining the state.
2. Key: define the state "ending at i." Defining dp[i] as "the LIS of the first i" is hard to transition; "the LIS length ending at nums[i]" connects cleanly:
   • State: dp[i] = longest increasing subsequence ending at nums[i].
   • Transition: dp[i] = max(dp[j] + 1) over all j < i with nums[j] < nums[i]; else dp[i] = 1.
   • Answer: max(dp) (not dp[n-1] — the longest may end in the middle).
3. Optimum (O(n²)): a double loop.

def lengthOfLIS(nums):
    dp = [1] * len(nums)              # each element alone is length 1
    for i in range(len(nums)):
        for j in range(i):
            if nums[j] < nums[i]:
                dp[i] = max(dp[i], dp[j] + 1)
    return max(dp)

int lengthOfLIS(vector<int>& nums) {
    vector<int> dp(nums.size(), 1);
    for (int i = 0; i < (int)nums.size(); i++)
        for (int j = 0; j < i; j++)
            if (nums[j] < nums[i])
                dp[i] = max(dp[i], dp[j] + 1);
    return *max_element(dp.begin(), dp.end());
}

💡 Advanced: O(n log n) patience sorting

import bisect
def lengthOfLIS(nums):
    tails = []                       # tails[k] = smallest tail of an LIS of length k+1
    for n in nums:
        i = bisect.bisect_left(tails, n)
        if i == len(tails):
            tails.append(n)
        else:
            tails[i] = n             # keep tails as small as possible
    return len(tails)

tails keeps "the smallest tail of an increasing subsequence of length k," with binary-search insertion, overall O(n log n).

• Complexity: DP O(n²); patience O(n log n); O(n) space.
• Pitfall: ① define the state "ending at i" to transition cleanly; ② the answer is max(dp), not dp[-1]; ③ "strictly increasing" uses <; for "non-decreasing" use bisect_right.

⑤ LC 1143 — Longest Common Subsequence

📋 Problem: Given strings text1, text2, return the length of their longest common subsequence (not contiguous, but order-preserving).

Example: "abcde", "ace" → 3 ("ace"); "abc", "def" → 0

🧭 From reading the problem to the solution

1. Break it down: two strings, find a common one — classic 2D DP. The state is naturally "how far into each string."
2. Apply the framework:
   • State: dp[i][j] = LCS length of text1's first i chars and text2's first j chars.
   • Transition:
     • If text1[i-1] == text2[j-1] (last chars match) → dp[i][j] = dp[i-1][j-1] + 1.
     • Else → dp[i][j] = max(dp[i-1][j], dp[i][j-1]) (drop one's last char).
   • Base: dp[0][*] = dp[*][0] = 0 (empty string).
   • Answer: dp[m][n].
3. Key insight: 2D DP's essence is the fork "do the last chars match" — match → both +1, else step back and take the larger. LCS is the parent of "two-sequence DP" (edit distance, shortest common supersequence are variants).

def longestCommonSubsequence(text1, text2):
    m, n = len(text1), len(text2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if text1[i-1] == text2[j-1]:
                dp[i][j] = dp[i-1][j-1] + 1
            else:
                dp[i][j] = max(dp[i-1][j], dp[i][j-1])
    return dp[m][n]

int longestCommonSubsequence(string text1, string text2) {
    int m = text1.size(), n = text2.size();
    vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
    for (int i = 1; i <= m; i++)
        for (int j = 1; j <= n; j++)
            if (text1[i-1] == text2[j-1])
                dp[i][j] = dp[i-1][j-1] + 1;
            else
                dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
    return dp[m][n];
}

• Complexity: O(m·n) time, O(m·n) space (rollable to O(n)).
• Pitfall: ① size dp (m+1)×(n+1), with an extra ring for the empty-string base; ② string index text[i-1] maps to dp[i] — mind the off-by-one; ③ when last chars differ it's max(up, left), not dp[i-1][j-1].

The DP 5-Step Framework (one table)

Pattern-Recognition Cheats

• "how many ways / reach the end" → linear DP; think "where did the last step come from."
• "pick or skip, adjacency constraint" → choice transition max(pick, skip).
• "make a target, fewest/most used" → knapsack DP (not greedy).
• "longest/shortest subsequence" → define the state "ending at i."
• "two strings/sequences" → 2D DP, forking on "do the last elements match."

DP's essence isn't memorizing problems — it's making the 5-step framework reflexive: first ask what dp[i] is, then how it comes from smaller subproblems. Get the state right and the problem is more than half solved.