1. Fibonacci

Idea: Each number is the sum of the two before it.

0, 1, 1, 2, 3, 5, 8, 13, ...

fib[1] = 0, fib[2] = 1;
for (int i = 3; i <= n; i++) fib[i] = fib[i-1] + fib[i-2];

Trace for n=6:

fib[1] = 0
fib[2] = 1
fib[3] = fib[2] + fib[1] = 1+0 = 1
fib[4] = fib[3] + fib[2] = 1+1 = 2
fib[5] = fib[4] + fib[3] = 2+1 = 3
fib[6] = fib[5] + fib[4] = 3+2 = 5

Why DP? You reuse previously computed values instead of recalculating recursively every time.

2. Number of Ways (Staircase)

Problem: You're on step s, want to reach step e. Each move you can jump +1, +2, or +3 steps. How many ways?

dp[s] = 1;  // one way to be at start
for (int i = s+1; i <= e; i++) {
    if (i-1 >= s) dp[i] += dp[i-1];  // came from 1 step back
    if (i-2 >= s) dp[i] += dp[i-2];  // came from 2 steps back
    if (i-3 >= s) dp[i] += dp[i-3];  // came from 3 steps back
}

Trace for s=0, e=4:

dp[0] = 1
dp[1] = dp[0]           = 1
dp[2] = dp[1]+dp[0]     = 2
dp[3] = dp[2]+dp[1]+dp[0] = 4
dp[4] = dp[3]+dp[2]+dp[1] = 7

Intuition: To know how many ways to reach step i, just ask: how many ways were there to reach the 3 steps before it? Add them up.

3. Broken Steps

Problem: Same as above, but some steps are broken — you can't land on them.

if (broken[i]) continue;         // skip broken steps entirely
if (!broken[i-1] ...) dp[i] += dp[i-1];  // only add if that step is usable

Trace for s=0, e=4, broken={2}:

dp[0] = 1
dp[1] = dp[0] = 1
dp[2] → SKIP (broken)
dp[3] = dp[2](broken, skip) + dp[1] + dp[0] = 0+1+1 = 2
dp[4] = dp[3] + dp[2](broken=0) + dp[1] = 2+0+1 = 3

Key insight: A broken step contributes 0 ways because dp[broken] = 0 and we skip computing it. But we still need to avoid adding FROM broken steps, hence the !broken[i-k] checks.

4. LIS — Longest Increasing Subsequence

Problem: Given an array, find the length of the longest subsequence where each element is strictly greater than the previous.

Example:

[3, 1, 4, 1, 5, 9, 2, 6] → LIS is [1, 4, 5, 9] = length 4

dp[i] = 1;  // every element alone is a subsequence of length 1
for (int i = 0; i < n; i++)
    for (int o = 0; o < i; o++)
        if (s[o] < s[i])
            dp[i] = max(dp[i], dp[o] + 1);

Trace for [3, 1, 4, 2, 5]:

i=0: s[0]=3, dp[0]=1         → [3]
i=1: s[1]=1, nothing before is <1, dp[1]=1   → [1]
i=2: s[2]=4, s[0]=3<4 → dp[2]=dp[0]+1=2
              s[1]=1<4 → dp[2]=max(2,dp[1]+1)=2  → [1,4] or [3,4]
i=3: s[3]=2, s[1]=1<2 → dp[3]=dp[1]+1=2     → [1,2]
i=4: s[4]=5, s[0]=3<5 → dp[4]=2
              s[2]=4<5 → dp[4]=max(2,dp[2]+1)=3
              s[3]=2<5 → dp[4]=max(3,dp[3]+1)=3  → [1,4,5] or [1,2,5]

ans = max(1,1,2,2,3) = 3

Intuition: dp[i] = "what's the longest increasing subsequence that ends exactly at position i?" For each i, look back at all previous elements smaller than s[i] and extend the best one.

Link: https://cses.fi/problemset/task/1145

5. Grid Max Path

Problem: Given an n×m grid with values, start at top-left (1,1), reach bottom-right (n,m). You can only move right or down. Maximize the sum of values collected.

dp[1][1] = s[1][1];
// first column: can only come from above
for (int i = 2; i <= n; i++) dp[i][1] = dp[i-1][1] + s[i][1];
// first row: can only come from left
for (int i = 2; i <= m; i++) dp[1][i] = dp[1][i-1] + s[1][i];
// rest: come from above or left, pick better
for (int i = 2; i <= n; i++)
    for (int o = 2; o <= m; o++)
        dp[i][o] = max(dp[i-1][o], dp[i][o-1]) + s[i][o];

Trace for grid:

Grid:          dp table:
1  3  2        1   4   6
4  2  1  →     5   7   8
2  1  3        7   8  11

Step by step:

dp[1][1]=1, dp[1][2]=4, dp[1][3]=6
dp[2][1]=5, dp[3][1]=7
dp[2][2]=max(dp[1][2], dp[2][1])+2 = max(4,5)+2 = 7
dp[2][3]=max(dp[1][3], dp[2][2])+1 = max(6,7)+1 = 8
dp[3][2]=max(dp[2][2], dp[3][1])+1 = max(7,7)+1 = 8
dp[3][3]=max(dp[2][3], dp[3][2])+3 = max(8,8)+3 = 11

Intuition: Each cell can only be reached from the top or the left. Pick whichever path brought the higher sum, then add the current cell's value.

Link: https://cses.fi/problemset/task/1638 (or grid path variant)

6. Dice Combinations

Problem: How many ways can you make sum n by rolling a 6-sided die any number of times? Order matters — (1,2) and (2,1) are different.

dp[0] = 1;  // one way to make sum 0: roll nothing
for (int i = 1; i <= n; i++)
    for (int o = 1; o <= 6; o++)
        if (i - o >= 0)
            dp[i] += dp[i-o];   // mod 1e9+7

Trace for n=4:

dp[0] = 1
dp[1] = dp[0]                         = 1
dp[2] = dp[1]+dp[0]                   = 2
dp[3] = dp[2]+dp[1]+dp[0]             = 4
dp[4] = dp[3]+dp[2]+dp[1]+dp[0]       = 8

Intuition: To make sum i, the last die roll was some face o (1–6). Before that roll, the sum was i-o. So count all ways to make i-o and add them up. dp[0]=1 is the base — "empty sequence" has exactly one way.

Why mod 1e9+7? The numbers grow astronomically fast. Modulo keeps them from overflowing int.

Link: https://cses.fi/problemset/task/1633

The Universal DP Thought Process

Every DP problem follows the same 3 steps:

1. DEFINE  → what does dp[i] mean?
2. TRANSITION → how do I compute dp[i] from smaller values?
3. BASE CASE → what's the starting value I know for sure?

1. Minimum Coins (Coin Change)

Goal: Find the minimum number of coins needed to reach a given sum.

vector<int> dp(sum + 1, INT_MAX - 1);
dp[0] = 0;

for (int i = 1; i <= sum; i++) {
    for (auto it : s) {
        if (i - it >= 0)
            dp[i] = min(dp[i], dp[i - it] + 1);
    }
}

Idea: For every amount i, try using each coin. If using coin it improves the answer, update dp[i].

We always rely on a smaller subproblem dp[i - it] that is already computed.

2. Coin Combinations I — Order Matters

Goal: Count the number of ordered sequences of coins that sum to sum.

dp[0] = 1;

for (int i = 1; i <= sum; i++) {
    for (auto it : s) {
        if (i - it >= 0)
            dp[i] += dp[i - it];

        if (dp[i] >= 1e9 + 7)
            dp[i] -= 1e9 + 7;
    }
}

Key observation: Loop order is:

amount → coins

This means different orders are counted separately, so [1,3] and [3,1] are different solutions.

3. Coin Combinations II — Order Doesn't Matter

Goal: Count unordered combinations of coins.

dp[0] = 1;

for (auto it : s) {
    for (int i = 1; i <= sum; i++) {
        if (i - it >= 0)
            dp[i] += dp[i - it];

        if (dp[i] >= 1e9 + 7)
            dp[i] -= 1e9 + 7;
    }
}

Key observation: Loop order becomes:

coins → amount

Each coin is processed fully before moving to the next one, therefore permutations collapse into a single combination.

4. Removing Digits

Goal: Starting from n, repeatedly subtract one of its digits until reaching 0. Find the minimum number of steps.

vector<int> dp(n + 1, INT_MAX - 1);
dp[n] = 0;

for (int i = n; i >= 0; i--) {
    if (dp[i] == INT_MAX - 1) continue;

    int x = i;
    while (x) {
        int dig = x % 10;
        x /= 10;

        if (dig && i - dig >= 0)
            dp[i - dig] = min(dp[i - dig], dp[i] + 1);
    }
}

Important note: The loop must be i >= 0, not i >= n.

Idea: From every reachable number, try subtracting each of its digits and update the result if a shorter path is found.

5. Book Shop (0/1 Knapsack)

Goal: Maximize total pages without exceeding budget x. Each book can be chosen at most once.

int dp[100005] = {};

for (int i = 0; i < n; i++) {
    for (int o = x; o >= 1; o--) {
        if (o >= p[i])
            dp[o] = max(dp[o], dp[o - p[i]] + h[i]);
    }
}

Why iterate backwards?

Iterating from x downwards guarantees that every item is used only once. Forward iteration would allow reusing the same item multiple times (unbounded knapsack).

Quick Reference