Chapter 6.1: Introduction to Dynamic Programming

📝 Prerequisites: 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 "smart recursion with memory." Let's build this intuition from scratch using the simplest example: the Fibonacci sequence.

💡 Key idea: 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 properties hold, DP can turn exponential time into polynomial time.

📚 Chapter Roadmap

🧭 Suggested reading path: If you are new to DP, read §6.1.1–§6.1.4 in order and make sure you can explain "why caching works" and "how the table is filled." If you already know basic DP, jump to §6.1.7–§6.1.8 and focus on deriving states from problem statements.

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 is computed, reducing 2^N calls to only N unique calls — this is the fundamental insight behind dynamic programming.

Naive recursive implementation:

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

This is correct, but terribly slow:

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, and fib(2) is computed three times. For fib(50), the number of calls exceeds 10^10. This is exponential time: O(2^n).

Core insight: we are repeatedly computing the same subproblems. DP solves this problem.

6.1.2 Memoization (Top-Down DP)

Memoization = recursion + cache. Before computing a value, check whether it has already been computed. If yes, return the cached result; if no, compute it, store it, and return it.

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

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);  // initialize all values to -1 ("not computed" marker)
    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, then 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;
}

Manual trace: how the dp array changes

When you only read the code, it is easy to know that "the loop is correct," but not understand how the array is actually filled. For n = 6, the dp array changes like this:

This table is the real execution process of the tabulation code: each loop iteration fills exactly one new cell, and it only depends on old cells that have already been filled.

We can even optimize space: since each Fibonacci number only depends on the previous two values, 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

Comparing the two approaches on fib(4):

💡 Key difference: Top-down computes on demand (only the subproblems that are needed), while bottom-up fills the whole table (all subproblems in order). They have the same time complexity, but bottom-up has no recursion stack overhead.

🏆 USACO tip: In contests, bottom-up tabulation is slightly preferred because it avoids possible stack overflow (important for problems with N = 10^5) and is usually faster. But if you cannot see the recurrence clearly, start with top-down — it is a great way to think.

6.1.4 The Four-Step DP Method

Every DP problem follows the same method:

The four-step DP method — from state definition to space optimization:

1. Define the state: What information uniquely describes a subproblem?
2. Define the transition: How does dp[state] depend on smaller states?
3. Determine base cases: What are the answers to the simplest subproblems?
4. Determine the order: In what order should the table be filled?

Applied to Fibonacci:

1. State: dp[i] = the i-th Fibonacci number
2. Transition: 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 state depends on smaller i)

The 5th step you should add when learning DP: manual tracing

Many DP problems become clear after you understand the state and transition, but students still get stuck because they do not know how the dp array changes step by step while the loops run.

So whenever you learn a new DP problem, take a very small sample and manually draw:

1. What the initial array looks like. Which positions are 0, which are INF, and which are "impossible."
2. Which states are newly created or updated after each outer-loop step. For example, after finishing i = 3, what are the values in dp[0..3]?
3. Why a certain cell becomes this value. Which old state did it come from? Did it take min, max, or another operation among several candidates?
4. Where the final answer is taken from. Is it dp[n], or do you need to take a maximum/minimum over several states?

Later examples in this chapter include more of these manual trace tables to help you connect recurrence formulas with real code execution.

6.1.5 Coin Change — Classic DP

Problem: Given coin denominations coins[], what is the minimum number of coins needed to make amount W? You can use each denomination unlimited times.

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

First try greedy (always choose the largest coin ≤ the remaining amount):

• Greedy: 9 + 1 + 1 = 3 coins ← not optimal!
• Optimal: 5 + 6 = 2 coins ← DP can find it

This is why greedy fails here and why we need DP.

Visual: Coin Change DP Table

The DP table shows how dp[i] (the minimum number of coins needed to make amount i) is filled from left to right. For coins {1,3,4}, notice that dp[3]=1 (use coin 3 directly) and dp[6]=2 (use two 3-coins).

DP definition

State transitions for coins = {1, 5, 6}:

• State: dp[w] = the minimum number of coins needed to make exactly amount w
• Transition: dp[w] = 1 + min(for every coin c ≤ w: dp[w - c]) (use coin c, then solve the remaining amount w-c optimally)
• Base case: dp[0] = 0 (making amount 0 needs 0 coins)
• Answer: dp[W]
• Order: w from 1 to W

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

dp[0] = 0 (base case)

dp[1]:  use coin 1: dp[0]+1=1          → dp[1] = 1
dp[2]:  use coin 1: dp[1]+1=2          → dp[2] = 2
...
dp[5]:  use coin 1: dp[4]+1=5
         use coin 5: dp[0]+1=1          → dp[5] = 1  ← use the 5-coin!
dp[6]:  use coin 1: dp[5]+1=2
         use coin 5: dp[1]+1=2
         use coin 6: dp[0]+1=1          → dp[6] = 1  ← use the 6-coin!
...
dp[11]: use coin 5: dp[6]+1=2
         use coin 6: dp[5]+1=2          → 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) ✓

Manual trace: the dp array after each amount

The table below shows how dp[0..11] changes for coins = [1, 5, 6, 9] and W = 11 after the outer loop finishes each amount w. ∞ means the amount cannot currently be formed.

Notice that the values at w = 5, w = 6, and w = 9 suddenly become small because those amounts can use a coin of denomination 5, 6, or 9 directly.

// 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 needed to make w
    dp[0] = 0;                    // base case

    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
            }
        }
    }

    if (dp[W] == INF) {
        cout << "Impossible\n";
    } else {
        cout << dp[W] << "\n";
    }

    return 0;
}

Complexity analysis:

• Time: O(N × W) — for each amount w (1..W), try all N coin types
• Space: O(W) — only the dp array is needed

6.1.6 Number of Ways — Coin Change Variant

Problem: Using the given coins, how many different ways are there to make amount W? Each coin denomination can be used unlimited times.

This type of problem is similar to "minimum number of coins," but the goal changes:

• Minimum number of coins: take min.
• Number of ways: take sum.

First define the state: what does ways[w] mean?

ways[w] = number of ways to make amount w

The most important base case is:

ways[0] = 1;

This may feel counterintuitive at first: why is there 1 way to make amount 0?

Because it represents the empty choice: choosing nothing. It gives later transitions a starting point. For example, if there is a coin 5, then:

ways[5] += ways[5 - 5]
ways[5] += ways[0]

If ways[0] were not 1, we could not correctly create the one way "use only one 5-coin."

Case 1: ordered number of ways (permutations)

Ordered means order matters: [1, 5] and [5, 1] are two different ways.

Here we think in terms of "what is the last coin?"

If we want to make amount w, the last coin could be any coin c. The previous part must make w - c:

ways[w] += ways[w - c]

Code:

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

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

Notice that the outer loop is amount w. This means we compute ways[1], ways[2], ways[3], ... in order. For each ways[w], we try placing every coin as the last coin.

Manual trace: ordered number of ways

Use coins = [1, 2], W = 4.

So when order matters, the 5 ways to make 4 are:

1 + 1 + 1 + 1
1 + 1 + 2
1 + 2 + 1
2 + 1 + 1
2 + 2

You can see that 1 + 1 + 2, 1 + 2 + 1, and 2 + 1 + 1 are counted as three different ways because their orders differ.

Case 2: unordered number of ways (combinations)

Unordered means order does not matter: [1, 5] and [5, 1] are the same way.

Now we cannot count by "last coin," because that would count different orders repeatedly. Instead, we use a different idea: introduce coin types one by one.

Code:

vector<long long> ways(W + 1, 0);
ways[0] = 1;

for (int c : coins) {               // outer loop: coin type
    for (int w = c; w <= W; w++) {   // inner loop: amount
        ways[w] += ways[w - c];
    }
}

This code means:

• After processing coin 1, ways[w] means "the number of ways to make w using only coin 1."
• After processing coin 2, ways[w] means "the number of ways to make w using only coins 1 and 2."
• If there is also coin 5, then after processing it, ways[w] means "the number of ways to make w using only coins 1, 2, and 5."

Because coin types are introduced in a fixed order, the same set of coins will not be counted again just because the order changed.

Manual trace: unordered number of ways

Again use coins = [1, 2], W = 4.

So when order does not matter, the 3 ways to make 4 are:

1 + 1 + 1 + 1
1 + 1 + 2
2 + 2

Here 1 + 2 + 1 and 2 + 1 + 1 are not counted separately, because they use the same multiset of coins as 1 + 1 + 2.

Why does simply swapping two loops change the answer?

The key is that ways[w] has different meanings during the loop.

One-sentence memory trick:

Amount on the outside enumerates the "last step," so it counts order; coin on the outside enumerates "which coin types are allowed," so it does not count order.

Understanding duplicate counting with [1, 5] and [5, 1]

Suppose coins = [1, 5] and we want to make 6.

In the ordered version, while computing ways[6]:

• If the last coin is 1, it comes from ways[5], which contains [5], so we get [5, 1].
• If the last coin is 5, it comes from ways[1], which contains [1], so we get [1, 5].

So [1, 5] and [5, 1] are counted separately.

In the unordered version, we first process coin 1, then coin 5. When processing coin 5, we only append 5 to methods already formed by coin 1, producing the single combination {1, 5}. We do not count the reversed order again.

Common pitfalls

1. Forgetting ways[0] = 1. Then all method counts become 0, because there is no starting point.
2. Reversing the loop order for permutations vs combinations. If the statement says "different order counts as different," put amount in the outer loop; if it says "coin combination," put coin type in the outer loop.
3. The number of ways may be large. Problems often ask you to take modulo some number, such as 1e9 + 7; in that case, apply % MOD after every addition.

6.1.7 Four Questions for State Design: From Problem Statement to DP Table

Many students find DP hard not because the code is difficult, but because they do not know what dp[...] should represent. When you see a new problem, do not rush to write a recurrence. First break it down with these four questions:

💡 State design rule: A dp state must contain exactly the information needed to determine the future. Too little information makes transitions impossible; too much information causes memory or time explosion.

6.1.8 USACO Real Problem Practice: State Design in Action

Real Problem 1: Hoof, Paper, Scissors (USACO 2017 January Gold) — Three-Dimensional State DP

Problem link: USACO 2017 January Gold P2: Hoof, Paper, Scissors
Pattern: sequence DP + limited state switching
Difficulty level: Gold intro

Problem interpretation

Bessie and FJ play N rounds of Hoof, Paper, Scissors. The three gestures are H (Hoof), P (Paper), and S (Scissors). The winning relationship is: H beats S, P beats H, and S beats P.

FJ's gestures for the next N rounds are known in advance. Bessie can use this full sequence to plan her gesture for every round, but she may change gestures at most K times. Choosing the initial gesture before round 1 does not count as a change; after that, a change is counted only when Bessie's gesture in round i differs from her gesture in round i-1. The goal is to maximize the number of rounds Bessie wins.

For example, if K = 0, Bessie must use the same gesture for the entire game. If K = 1, she can use one gesture for a consecutive prefix, then switch once to another gesture for the remaining rounds.

Key conditions:

• N is large, so we cannot enumerate all gesture sequences.
• K is small, suggesting that "how many changes have been used" should be a DP dimension.
• The current gesture affects whether the next round counts as a change, so we must also remember the current gesture.

Idea

State definition:

dp[i][j][g] = after processing the first i rounds,
              using j changes,
              currently using gesture g,
              the maximum number of wins

At round i, Bessie can:

• Continue using gesture g: the number of changes does not increase.
• Switch from another gesture to g: the number of changes increases by 1.

Each round also adds whether g beats FJ's gesture in round i.

Manual trace: how three-dimensional states change

A 3D array is hard to draw fully, so we view dp[i][used][g] in layers by used. Use this small sample:

N = 4, K = 1
FJ = H S H P

In the table, [H, P, S] stores the maximum wins when Bessie's current gesture is H/P/S; - means the state is impossible.

When reading this table, focus on two actions:

• Do not switch: For example, at i = 3, used = 0, P, it comes from the previous round's used = 0, P, then adds 1 because P beats H, so it becomes 2.
• Switch gesture: For example, at i = 4, used = 1, S, it can come from the previous round's used = 0, P. The previous best score for P is 2, and this round S beats P, so we add 1 and get 3.

The final answer is the maximum over all used <= K and all current gestures, which is 3.

Complete CPP code

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

int gestureId(char c) {
    if (c == 'H') return 0;
    if (c == 'P') return 1;
    return 2;  // 'S'
}

bool win(int bessie, int fj) {
    // H beats S, P beats H, S beats P
    return (bessie == 0 && fj == 2) ||
           (bessie == 1 && fj == 0) ||
           (bessie == 2 && fj == 1);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    // USACO official file I/O can be enabled when needed:
    // freopen("hps.in", "r", stdin);
    // freopen("hps.out", "w", stdout);

    int n, k;
    cin >> n >> k;
    vector<int> fj(n + 1);
    for (int i = 1; i <= n; i++) {
        char c;
        cin >> c;
        fj[i] = gestureId(c);
    }

    const int NEG = -1e9;
    vector dp(n + 1, vector(k + 1, vector<int>(3, NEG)));

    // In round 1, Bessie may directly choose any gesture; this does not count as a change
    for (int g = 0; g < 3; g++) {
        dp[1][0][g] = win(g, fj[1]) ? 1 : 0;
    }

    for (int i = 2; i <= n; i++) {
        for (int used = 0; used <= k; used++) {
            for (int cur = 0; cur < 3; cur++) {
                int score = win(cur, fj[i]) ? 1 : 0;

                // Do not switch gestures
                dp[i][used][cur] = max(dp[i][used][cur], dp[i - 1][used][cur] + score);

                // Switch from another gesture to cur
                if (used > 0) {
                    for (int prev = 0; prev < 3; prev++) {
                        if (prev == cur) continue;
                        dp[i][used][cur] = max(dp[i][used][cur], dp[i - 1][used - 1][prev] + score);
                    }
                }
            }
        }
    }

    int answer = 0;
    for (int used = 0; used <= k; used++) {
        for (int g = 0; g < 3; g++) {
            answer = max(answer, dp[n][used][g]);
        }
    }

    cout << answer << "\n";
    return 0;
}

Common pitfalls

1. Treating "at most K" as "exactly K." The final answer should enumerate used = 0..K.
2. Wrong initial state. In round 1, Bessie can directly choose any gesture, and this does not count as a change; therefore initialize dp[1][0][g] to the round-1 score.
3. Reversing the winning relationship. H/P/S is like rock-paper-scissors but with different names; writing a separate win() function is recommended.
4. Missing the current gesture in the state. If you only write dp[i][j], you cannot know whether the next round switches gestures.

Extension

If the number of gestures grows from 3 to M, the complexity becomes O(NKM^2). You can optimize the switch transition to O(NKM) by maintaining the maximum and second maximum value for each used layer.

Real Problem 2: Teamwork (USACO 2018 December Gold) — Enumerating the Last Group

Problem link: USACO 2018 December Gold P3: Teamwork
Pattern: one-dimensional DP + enumerate the last segment
Difficulty level: Gold intro

Problem interpretation

N cows stand in a line, and each cow has a skill value. We can divide consecutive cows into groups, where each group has length at most K. In one group, every cow's contribution becomes the maximum skill value inside that group. Find the maximum total contribution.

Key conditions:

• Groups must be contiguous segments.
• Each group has length at most K.
• The contribution of a segment is length × max skill in the segment.

Idea

Consider cows from left to right. Define:

dp[i] = the maximum total contribution after fully grouping the first i cows

The last group may have length len = 1..K, covering [i-len+1, i]. If we enumerate the length of the last group, the problem becomes:

dp[i] = max(dp[i-len] + len * max(skill[i-len+1..i]))

While enumerating len, maintain the current segment maximum at the same time, so we do not rescan the segment each time.

Manual trace: how dp[i] is updated step by step

Use this small sample:

N = 5, K = 3
skill = [1, 15, 7, 9, 2]

dp[i] means the maximum total contribution after the first i cows have been fully grouped. Each row enumerates the possible length of the "last group."

This table corresponds to the inner loop in the code: len increases from 1 to K, and groupMax maintains the maximum skill in the last group as it expands leftward.

Complete CPP code

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    // USACO official file I/O can be enabled when needed:
    // freopen("teamwork.in", "r", stdin);
    // freopen("teamwork.out", "w", stdout);

    int n, k;
    cin >> n >> k;
    vector<int> skill(n + 1);
    for (int i = 1; i <= n; i++) cin >> skill[i];

    vector<int> dp(n + 1, 0);

    for (int i = 1; i <= n; i++) {
        int groupMax = 0;
        for (int len = 1; len <= k && i - len + 1 >= 1; len++) {
            groupMax = max(groupMax, skill[i - len + 1]);
            dp[i] = max(dp[i], dp[i - len] + groupMax * len);
        }
    }

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

Common pitfalls

1. The left endpoint of the last group goes out of bounds. The loop condition must include i - len + 1 >= 1.
2. Recomputing the interval maximum every time. This becomes O(NK^2); maintain groupMax while enumerating len.
3. Unclear state definition. dp[i] must mean "the first i cows are fully grouped," so dp[i-len] can connect cleanly to the last group.
4. Mistaking it for greedy. Always expanding around strong cows as much as possible is not necessarily optimal, because it changes group boundaries for later cows.

Extension

Teamwork is a classic example of "enumerate the last segment" DP. Similar patterns appear in array partitioning, text wrapping, and interval segmentation optimization. The signal is: the answer consists of several contiguous segments, each segment has an independent contribution, and segment length is limited.

⚠️ Common Mistakes in Chapter 6.1

1. Initializing dp with 0 instead of INF for minimization problems: dp[w] = 0 means "0 coins," and it will never be improved. Use dp[w] = INF, with only dp[0] = 0.
2. Using dp[w-c] without checking dp[w-c] != INF: INF + 1 may overflow! Always check whether the subproblem is solvable.
3. Wrong loop order for knapsack variants: For unbounded knapsack (unlimited coins), iterate amounts forward; for 0/1 knapsack (each item used once), iterate amounts backward. Mixing this up produces silent wrong answers.
4. Using INT_MAX as INF and then adding 1: INT_MAX + 1 overflows into a negative number. Use 1e9 or 1e18 as INF.
5. Forgetting base cases: dp[0] = 0 is crucial. Without it, nothing can be initialized correctly.

Chapter Summary

📌 Key takeaways

🧩 DP four-step method quick reference

❓ FAQ

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

A: Look for two signals: ① the problem asks for an "optimal value" or "number of ways" (not "output the concrete 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 unnecessary; otherwise, it is likely DP.

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

A: When learning, use top-down (it expresses recursive thinking more naturally). For contest submissions, use bottom-up (faster, no stack overflow). Both are correct. If you can quickly write bottom-up, use it directly.

Q3: What is "optimal substructure" / "no aftereffect"?

A: It is the core prerequisite for DP — once dp[i] is determined, future computations will not come back and change it. In other words, dp[i] only depends on the "past" (smaller states), not the "future." If this property is violated, DP cannot be applied directly.

Q4: What should INF be?

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

🔗 Connections to later chapters

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

Practice Problems

Problem 6.1.1 — Climbing Stairs 🟢 Easy Each time you may climb 1 or 2 stairs. How many ways are there to climb N stairs?

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n; cin >> n;
    if (n == 1) { cout << 1; return 0; }
    vector<long long> dp(n + 1);
    dp[1] = 1; dp[2] = 2;
    for (int i = 3; i <= n; i++)
        dp[i] = dp[i-1] + dp[i-2];
    cout << dp[n] << "\n";
}

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

#include <bits/stdc++.h>
using namespace std;
int main() {
    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[0] = 0;
    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);
        }
    }
    cout << (dp[W] == INF ? -1 : dp[W]) << "\n";
}

Problem 6.1.3 — Tile Tiling 🟡 Medium Use 1×2 dominoes (placed horizontally or vertically) to tile a 2×N board. How many ways?

#include <bits/stdc++.h>
using namespace std;
const long long MOD = 1e9 + 7;
int main() {
    int n; cin >> n;
    if (n == 1) { cout << 1; return 0; }
    vector<long long> dp(n + 1);
    dp[1] = 1; dp[2] = 2;
    for (int i = 3; i <= n; i++)
        dp[i] = (dp[i-1] + dp[i-2]) % MOD;
    cout << dp[n] << "\n";
}

Problem 6.1.4 — Coin Change with Limited Use 🔴 Hard Same as coin change, but each coin may be used at most once (0/1 knapsack). Find the minimum number of coins.

#include <bits/stdc++.h>
using namespace std;
int main() {
    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[0] = 0;
    for (int i = 0; i < n; i++) {
        // Reverse order: prevents coin i from being used more than once
        for (int w = W; w >= coins[i]; w--) {
            if (dp[w - coins[i]] != INF)
                dp[w] = min(dp[w], dp[w - coins[i]] + 1);
        }
    }
    cout << (dp[W] == INF ? -1 : dp[W]) << "\n";
}

Problem 6.1.5 — USACO Bronze: Haybale Stacking 🔴 Hard There are N operations of the form "add 1 to all positions from L to R." Find the final value at every position.

#include <bits/stdc++.h>
using namespace std;
int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    int n, q; cin >> n >> q;
    vector<long long> diff(n + 2, 0);
    while (q--) {
        int l, r; cin >> l >> r;
        diff[l]++;
        diff[r + 1]--;
    }
    long long cur = 0;
    for (int i = 1; i <= n; i++) {
        cur += diff[i];
        cout << cur << " \n"[i == n];
    }
}

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

#include <bits/stdc++.h>
using namespace std;
const long long MOD = 1e9 + 7;
int main() {
    int n, m; cin >> n >> m;
    vector<string> grid(n);
    for (auto& row : grid) cin >> row;
    vector<vector<long long>> dp(n, vector<long long>(m, 0));
    if (grid[0][0] == '.') dp[0][0] = 1;

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (grid[i][j] == '#') {
                dp[i][j] = 0;
                continue;
            }
            if (i > 0) dp[i][j] = (dp[i][j] + dp[i - 1][j]) % MOD;
            if (j > 0) dp[i][j] = (dp[i][j] + dp[i][j - 1]) % MOD;
        }
    }

    cout << dp[n - 1][m - 1] << "\n";
    return 0;
}