Chapter 6.1: Introduction to Dynamic Programming

📝 Before You Continue: Make sure you understand recursion (Chapter 2.3), arrays/vectors (Chapters 2.3–3.1), and basic loop patterns (Chapter 2.2). DP builds directly on recursion concepts.

Dynamic programming (DP) is often described as "clever recursion with memory." Let's build up this intuition from scratch, starting with the simplest possible example: Fibonacci numbers.

💡 Key Insight: DP solves problems with two properties:

1. Overlapping subproblems — the same sub-computation appears many times
2. Optimal substructure — the optimal solution to a big problem can be built from optimal solutions to smaller problems

When both are true, DP transforms exponential time into polynomial time.

6.1.1 The Problem with Naive Recursion

The Fibonacci sequence: 0, 1, 1, 2, 3, 5, 8, 13, 21, ...

Definition: F(0) = 0, F(1) = 1, F(n) = F(n-1) + F(n-2) for n ≥ 2.

Visual: Fibonacci Recursion Tree and Memoization

The recursion tree for fib(5) exposes the problem: fib(3) is computed twice (red nodes). Memoization caches each result the first time it's computed, reducing 2^N calls to just N unique calls — the fundamental insight behind dynamic programming.

The static diagram above shows how memoization eliminates redundant computations: each unique subproblem is solved only once and its result is cached for future lookups.

The naïve recursive implementation:

int fib(int n) {
    if (n == 0) return 0;
    if (n == 1) return 1;
    return fib(n-1) + fib(n-2);  // recursive
}

This is correct, but devastatingly slow. Let's see why:

fib(5)
├── fib(4)
│   ├── fib(3)
│   │   ├── fib(2)
│   │   │   ├── fib(1) = 1
│   │   │   └── fib(0) = 0
│   │   └── fib(1) = 1
│   └── fib(2)           ← COMPUTED AGAIN!
│       ├── fib(1) = 1
│       └── fib(0) = 0
└── fib(3)               ← COMPUTED AGAIN!
    ├── fib(2)            ← COMPUTED AGAIN!
    │   ├── fib(1) = 1
    │   └── fib(0) = 0
    └── fib(1) = 1

fib(3) is computed twice. fib(2) three times. For fib(50), the number of calls exceeds 10^10. This is exponential time: O(2^n).

The core insight: we're recomputing the same subproblems over and over. DP fixes this.

6.1.2 Memoization (Top-Down DP)

Memoization = recursion + cache. Before computing, check if we've already computed this value. If yes, return the cached result. If no, compute it, cache it, return it.

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 100;
long long memo[MAXN];  // memo[n] = F(n), or -1 if not yet computed
bool computed[MAXN];   // track which values are computed

long long fib_memo(int n) {
    if (n == 0) return 0;
    if (n == 1) return 1;
    if (computed[n]) return memo[n];  // already computed? return cached value

    memo[n] = fib_memo(n-1) + fib_memo(n-2);  // compute and cache
    computed[n] = true;
    return memo[n];
}

int main() {
    memset(computed, false, sizeof(computed));  // initialize cache as empty

    for (int i = 0; i <= 20; i++) {
        cout << "F(" << i << ") = " << fib_memo(i) << "\n";
    }
    return 0;
}

Or using -1 as the sentinel:

📝 说明： 以下是与上文 fib_memo 等价的另一种写法。区别在于：① 用 -1 作为"未计算"的哨兵值，省去单独的 computed[] 数组；② 函数名改为 fib，写法更简洁。两种写法在功能上完全相同，请勿将两种写法的代码片段混用（它们各自拥有独立的全局 memo 数组）。

// 写法二：-1 哨兵值（等价于上文 fib_memo，更简洁）
const int MAXN = 100;
long long memo[MAXN];

long long fib(int n) {
    if (n <= 1) return n;
    if (memo[n] != -1) return memo[n];
    return memo[n] = fib(n-1) + fib(n-2);
}

int main() {
    fill(memo, memo + MAXN, -1LL);  // 将所有值初始化为 -1（"未计算"标记）
    cout << fib(50) << "\n";        // 12586269025
    return 0;
}

Now each value is computed exactly once. Time complexity: O(N). 🎉

6.1.3 Tabulation (Bottom-Up DP)

Tabulation builds the answer from the ground up — compute small subproblems first, use them to compute larger ones.

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n = 50;
    vector<long long> dp(n + 1);

    // Base cases
    dp[0] = 0;
    dp[1] = 1;

    // Fill the table bottom-up
    for (int i = 2; i <= n; i++) {
        dp[i] = dp[i-1] + dp[i-2];  // use already-computed values
    }

    cout << dp[n] << "\n";  // 12586269025
    return 0;
}

We can even optimize space: since each Fibonacci number only depends on the previous two, we only need O(1) space:

long long a = 0, b = 1;
for (int i = 2; i <= n; i++) {
    long long c = a + b;
    a = b;
    b = c;
}
cout << b << "\n";

Memoization vs. Tabulation

两种方式的执行路径对比（以 fib(4) 为例）：

flowchart LR
    subgraph topdown["🔽 Top-Down（记忆化递归）"]
        direction TB
        F4a(["fib(4)"])
        F3a(["fib(3)"])
        F2a(["fib(2)"])
        F1a(["fib(1)=1"])
        F0a(["fib(0)=0"])
        F2b(["fib(2)\n📦 缓存命中!"])
        F4a --> F3a
        F4a --> F2b
        F3a --> F2a
        F3a --> F1a
        F2a --> F1a
        F2a --> F0a
        style F2b fill:#dcfce7,stroke:#16a34a
    end
    subgraph bottomup["🔼 Bottom-Up（制表法）"]
        direction LR
        D0["dp[0]=0"] --> D1["dp[1]=1"] --> D2["dp[2]=1"] --> D3["dp[3]=2"] --> D4["dp[4]=3"]
        note["顺序填表，每格只算一次"]
    end
    style topdown fill:#f0f4ff,stroke:#4A6CF7
    style bottomup fill:#f0fdf4,stroke:#16a34a

💡 核心区别： Top-Down 按需计算（只算用到的子问题），Bottom-Up 全量填表（按顺序算所有子问题）。两者时间复杂度相同，但 Bottom-Up 无递归栈开销。

🏆 USACO Tip: In competition, bottom-up tabulation is slightly preferred because it avoids potential stack overflow (critical on problems with N = 10^5) and is often faster. But start with top-down if you're having trouble seeing the recurrence — it's a great way to think through the problem.

In competitive programming, both are valid. Practice both until you can convert easily between them.

6.1.4 The DP Recipe

Every DP problem follows the same recipe:

DP 四步法流程图：

flowchart TD
    S1["① 定义状态\ndp[i] 代表什么？"] --> S2
    S2["② 写出递推关系\ndp[i] 如何由更小的状态得到？"] --> S3
    S3["③ 确定边界条件\n最小子问题的答案是什么？"] --> S4
    S4["④ 确定填表顺序\n从小到大？从大到小？"] --> S5
    S5{"能否压缩空间？"}
    S5 -->|"只依赖前1-2行"| S6["滚动数组 / 1D 优化"]
    S5 -->|"依赖整个表"| S7["保留完整 2D 表"]
    style S1 fill:#dbeafe,stroke:#3b82f6
    style S2 fill:#dbeafe,stroke:#3b82f6
    style S3 fill:#dbeafe,stroke:#3b82f6
    style S4 fill:#dbeafe,stroke:#3b82f6
    style S6 fill:#dcfce7,stroke:#16a34a

1. Define the state: What information uniquely describes a subproblem?
2. Define the recurrence: How does dp[state] depend on smaller states?
3. Identify base cases: What are the simplest subproblems with known answers?
4. Determine order: In what order should we fill the table?

Let's apply this to Fibonacci:

1. State: dp[i] = the i-th Fibonacci number
2. Recurrence: dp[i] = dp[i-1] + dp[i-2]
3. Base cases: dp[0] = 0, dp[1] = 1
4. Order: i from 2 to n (each depends on smaller i)

6.1.5 Coin Change — Classic DP

Problem: You have coins of denominations coins[]. What is the minimum number of coins needed to make amount W? You can use each coin type unlimited times.

Example: coins = [1, 5, 6, 9], W = 11

Let's first try the greedy approach (always pick the largest coin ≤ remaining):

• Greedy: 9 + 1 + 1 = 3 coins ← not optimal!
• Optimal: 5 + 6 = 2 coins ← DP finds this

This is why greedy fails here and we need DP.

Visual: Coin Change DP Table

The DP table shows how dp[i] (minimum coins to make amount i) is filled left to right. For coins {1,3,4}, notice that dp[3]=1 (just use coin 3) and dp[6]=2 (use two 3s). Each cell builds on previous cells using the recurrence.

This static reference shows the complete coin change DP table, with arrows indicating how each cell's value depends on previous cells via the recurrence dp[w] = 1 + min(dp[w-c]).

DP Definition

Coin Change 状态转移示意（coins=[1,5,6], W=7）：

flowchart LR
    D0(["dp[0]=0"]) 
    D1(["dp[1]=1"])
    D5(["dp[5]=1"])
    D6(["dp[6]=1"])
    D7(["dp[7]=2"])
    D0 -->|"用硬币1"| D1
    D0 -->|"用硬币5"| D5
    D0 -->|"用硬币6"| D6
    D1 -->|"用硬币6"| D7
    D5 -->|"用硬币1\ndp[5]+1=2"| D6_2(["dp[6]=min(1,2)=1"])
    D6 -->|"用硬币1\ndp[6]+1=2"| D7
    note1["dp[7] = min(dp[6]+1, dp[2]+1, dp[1]+1)\n     = min(2, ?, 2) = 2\n最优: 1+6 或 6+1"]
    style D0 fill:#f0fdf4,stroke:#16a34a
    style D7 fill:#dbeafe,stroke:#3b82f6
    style note1 fill:#fef9ec,stroke:#d97706

💡 转移方向： 每个 dp[w] 都从 dp[w-c]（用了硬币 c 之后的剩余金额）转移而来。箭头方向 = 状态依赖方向。

• State: dp[w] = minimum coins to make exactly amount w
• Recurrence: dp[w] = 1 + min over all coins c where c ≤ w: dp[w - c] (use coin c, then solve the remaining w-c optimally)
• Base case: dp[0] = 0 (zero coins to make amount 0)
• Answer: dp[W]
• Order: fill w from 1 to W

Complete Walkthrough: coins = [1, 5, 6, 9], W = 11

dp[0] = 0 (base case)

dp[1]:  try coin 1: dp[0]+1=1          → dp[1] = 1
dp[2]:  try coin 1: dp[1]+1=2          → dp[2] = 2
dp[3]:  try coin 1: dp[2]+1=3          → dp[3] = 3
dp[4]:  try coin 1: dp[3]+1=4          → dp[4] = 4
dp[5]:  try coin 1: dp[4]+1=5
        try coin 5: dp[0]+1=1          → dp[5] = 1  ← use the 5-coin!
dp[6]:  try coin 1: dp[5]+1=2
        try coin 5: dp[1]+1=2
        try coin 6: dp[0]+1=1          → dp[6] = 1  ← use the 6-coin!
dp[7]:  try coin 1: dp[6]+1=2
        try coin 5: dp[2]+1=3
        try coin 6: dp[1]+1=2          → dp[7] = 2  ← 1+6 or 6+1
dp[8]:  try coin 1: dp[7]+1=3
        try coin 5: dp[3]+1=4
        try coin 6: dp[2]+1=3          → dp[8] = 3
dp[9]:  try coin 1: dp[8]+1=4
        try coin 5: dp[4]+1=5
        try coin 6: dp[3]+1=4
        try coin 9: dp[0]+1=1          → dp[9] = 1  ← use the 9-coin!
dp[10]: try coin 1: dp[9]+1=2
        try coin 5: dp[5]+1=2
        try coin 6: dp[4]+1=5
        try coin 9: dp[1]+1=2          → dp[10] = 2  ← 1+9, 5+5, or 9+1
dp[11]: try coin 1: dp[10]+1=3
        try coin 5: dp[6]+1=2
        try coin 6: dp[5]+1=2
        try coin 9: dp[2]+1=3          → dp[11] = 2  ← 5+6 or 6+5!

dp table: [0, 1, 2, 3, 4, 1, 1, 2, 3, 1, 2, 2]

Answer: dp[11] = 2 (coins 5 and 6) ✓

// Solution: Minimum Coin Change — O(N × W)
#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, W;
    cin >> n >> W;

    vector<int> coins(n);
    for (int &c : coins) cin >> c;

    const int INF = 1e9;
    vector<int> dp(W + 1, INF);  // dp[w] = min coins to make w
    dp[0] = 0;                    // base case

    // Step 1: Fill dp table bottom-up
    for (int w = 1; w <= W; w++) {
        for (int c : coins) {
            if (c <= w && dp[w - c] != INF) {
                dp[w] = min(dp[w], dp[w - c] + 1);  // ← KEY LINE
            }
        }
    }

    // Step 2: Output result
    if (dp[W] == INF) {
        cout << "Impossible\n";
    } else {
        cout << dp[W] << "\n";
    }

    return 0;
}

Sample Input:

4 11
1 5 6 9

Sample Output:

2

Complexity Analysis:

• Time: O(N × W) — for each amount w (1..W), try all N coins
• Space: O(W) — just the dp array

Reconstructing the Solution

How do we print which coins were used? Track parent[w] = which coin was used last:

vector<int> dp(W + 1, INF);
vector<int> lastCoin(W + 1, -1);  // which coin gave optimal solution for w
dp[0] = 0;

for (int w = 1; w <= W; w++) {
    for (int c : coins) {
        if (c <= w && dp[w-c] + 1 < dp[w]) {
            dp[w] = dp[w-c] + 1;
            lastCoin[w] = c;   // record that coin c was used
        }
    }
}

// Trace back the solution
vector<int> solution;
int w = W;
while (w > 0) {
    solution.push_back(lastCoin[w]);
    w -= lastCoin[w];
}
for (int c : solution) cout << c << " ";
cout << "\n";

6.1.6 Number of Ways — Coin Change Variant

Problem: How many different ways can you make amount W using the given coins? (Order matters: [1,5] and [5,1] are different.)

// Ordered ways (permutations — order matters)
vector<long long> ways(W + 1, 0);
ways[0] = 1;  // one way to make 0: use no coins

for (int w = 1; w <= W; w++) {
    for (int c : coins) {
        if (c <= w) {
            ways[w] += ways[w - c];  // ← KEY LINE
        }
    }
}

If order doesn't matter (combinations — [1,5] same as [5,1]):

// Unordered ways (combinations — order doesn't matter)
vector<long long> ways(W + 1, 0);
ways[0] = 1;

for (int c : coins) {           // outer loop: coins (each coin is considered once)
    for (int w = c; w <= W; w++) {  // inner loop: amounts
        ways[w] += ways[w - c];
    }
}

💡 Key Insight: The order of loops matters for counting combinations vs. permutations! When coins are in the outer loop, each coin is "introduced" once and order is ignored. When amounts are in the outer loop, each amount is formed fresh each time, allowing all orderings.

⚠️ Common Mistakes in Chapter 6.1

1. Initializing dp with 0 instead of INF: For minimization problems, dp[w] = 0 means "0 coins" which will never get improved. Use dp[w] = INF and only dp[0] = 0.
2. Not checking dp[w-c] != INF before using it: INF + 1 overflows! Always check that the subproblem is solvable.
3. Wrong loop order for knapsack variants: For unbounded (unlimited coins), loop amounts forward. For 0/1 (each used once), loop amounts backward. Getting this wrong gives wrong answers silently.
4. Using INT_MAX as INF then adding 1: INT_MAX + 1 overflows to negative. Use 1e9 or 1e18 as INF.
5. Forgetting the base case: dp[0] = 0 is crucial. Without it, nothing ever gets set.

Chapter Summary

📌 Key Takeaways

🧩 DP Four-Step Method Quick Reference

❓ FAQ

Q1: How do I tell if a problem is a DP problem?

A: Two signals: ① the problem asks for an "optimal value" or "number of ways" (not "output the specific solution"); ② there are overlapping subproblems (the same subproblem is computed multiple times in brute-force recursion). If greedy can be proven correct, DP is usually not needed; otherwise it's likely DP.

Q2: Should I use top-down or bottom-up?

A: While learning, use top-down (more naturally expresses recursive thinking); for contest submission, use bottom-up (faster, no stack overflow). Both are correct. If you can quickly write bottom-up, go with it directly.

Q3: What is "optimal substructure" (no aftereffect)?

A: The core prerequisite of DP — once dp[i] is determined, subsequent computations will not "come back" to change it. In other words, dp[i]'s value only depends on the "past" (smaller states), not the "future". If this property is violated, DP cannot be used.

Q4: What value should INF be set to?

A: For int use 1e9 (= 10^9), for long long use 1e18 (= 10^18). Do not use INT_MAX, because INT_MAX + 1 overflows to a negative number.

🔗 Connections to Later Chapters

• Chapter 6.2 (Classic DP): extends to LIS, knapsack, grid paths — all applications of the four-step DP method from this chapter
• Chapter 6.3 (Advanced DP): enters bitmask DP, interval DP, tree DP — more complex state definitions but same thinking
• Chapter 3.2 (Prefix Sums): difference arrays can sometimes replace simple DP, and prefix sum arrays can speed up interval computations in DP
• Chapter 4.1 (Greedy) vs DP: greedy-solvable problems are a special case of DP (local optimum = global optimum at each step); when greedy fails, DP is needed

Practice Problems

Problem 6.1.1 — Climbing Stairs 🟢 Easy You can climb 1 or 2 stairs at a time. How many ways to climb N stairs? (Same as Fibonacci — ways[n] = ways[n-1] + ways[n-2])

Problem 6.1.2 — Minimum Coin Change 🟡 Medium Given coin denominations [1, 3, 4] and target 6, find the minimum coins. (Expected answer: 2 coins — use 3+3)

Problem 6.1.3 — Tile Tiling 🟡 Medium A 2×N board can be tiled with 1×2 dominoes (placed horizontally or vertically). How many ways?

Solution sketch: dp[n] = dp[n-1] + dp[n-2]. Vertical tile fills one column alone; two horizontal tiles fill two columns together.

Problem 6.1.4 — Bounded Coin Change 🔴 Hard Same as coin change, but you can use each coin at most once (0/1 knapsack). Find the minimum coins.

Solution sketch: Similar to 0/1 knapsack. Use a 2D dp[i][w] = min coins using first i coins to make w. Or the space-optimized version with backward iteration.

Problem 6.1.5 — USACO Bronze: Haybale Stacking 🔴 Hard Given N operations "add 1 to all positions from L to R", determine the final value at each position.

Use difference array from Chapter 3.2. This is also solvable by thinking of it as "build the answer" (DP-like perspective).

🏆 Challenge Problem: Unique Paths with Obstacles An N×M grid has '.' cells and '#' obstacles. Count paths from (1,1) to (N,M) moving only right or down. Answer modulo 10^9+7. (N, M ≤ 1000)

Visual: Fibonacci Recursion Tree

The diagram shows naive recursion for fib(6). Red dashed nodes are duplicate subproblems — computed multiple times. Green nodes show where memoization caches results. Without memoization: O(2^N). With memoization: O(N). This is the fundamental insight behind dynamic programming.