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.

Practice Problems

• CSES — Shortest Routes I https://cses.fi/problemset/task/1671/

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.

Practice Problems

• CSES — Dice Combinations https://cses.fi/problemset/task/1633/

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.

Practice Problems

• AtCoder Educational DP Contest — Frog 1 https://atcoder.jp/contests/dp/tasks/dp_a

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.

Practice Problems

• CSES — Increasing Subsequence https://cses.fi/problemset/task/1145/
• Codeforces 1352C — K-th Not Divisible by n https://codeforces.me/problemset/problem/1352/C

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.

Practice Problems

• CSES — Grid Paths https://cses.fi/problemset/task/1638/

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.

Practice Problems

• CSES — Dice Combinations https://cses.fi/problemset/task/1633/
• Codeforces 474D — Flowers https://codeforces.me/problemset/problem/474/D

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?