## 1. Fibonacci↵
↵
**Idea:** Each number is the sum of the two before it.↵
↵
```↵
0, 1, 1, 2, 3, 5, 8, 13, ...↵
```↵
↵
```cpp↵
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↵
↵
Link: https://cses.fi/problemset/task/1963 (or just classic Fibonacci)↵
↵
↵
---↵
↵
## 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?↵
↵
```cpp↵
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↵
↵
Link: https://cses.fi/problemset/task/1637↵
↵
---↵
↵
## 3. Broken Steps↵
↵
**Problem:** Same as above, but some steps are broken — you can't land on them.↵
↵
```cpp↵
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↵
↵
Link: https://cses.fi/problemset/task/1638↵
↵
---↵
↵
## 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↵
```↵
↵
```cpp↵
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↵
↵
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.↵
↵
```cpp↵
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↵
↵
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.↵
↵
```cpp↵
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↵
↵
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?↵
```↵
↵
| Problem | dp[i] means | Transition |↵
| --------- | ---------------------------- | ---------------------------- |↵
| Fibonacci | i-th fib number | `dp[i-1] + dp[i-2]` |↵
| Staircase | ways to reach step i | sum of 3 previous |↵
| LIS | LIS ending at index i | `max(dp[o]+1)` for s[o]<s[i] |↵
| Grid | best sum to reach cell (i,j) | `max(top, left) + val` |↵
| Dice | ways to make sum i | sum over 6 dice faces |↵
↵
↵
↵
**Idea:** Each number is the sum of the two before it.↵
↵
```↵
0, 1, 1, 2, 3, 5, 8, 13, ...↵
```↵
↵
```cpp↵
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.↵
↵
Link: https://cses.fi/problemset/task/1963 (or just classic Fibonacci)↵
↵
↵
---↵
↵
## 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?↵
↵
```cpp↵
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.↵
↵
```cpp↵
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↵
```↵
↵
```cpp↵
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.↵
↵
↵
↵
---↵
↵
## 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.↵
↵
```cpp↵
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.↵
↵
↵
↵
---↵
↵
## 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.↵
↵
```cpp↵
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.↵
↵
↵
↵
---↵
↵
## 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?↵
```↵
↵
| Problem | dp[i] means | Transition |↵
| --------- | ---------------------------- | ---------------------------- |↵
| Fibonacci | i-th fib number | `dp[i-1] + dp[i-2]` |↵
| Staircase | ways to reach step i | sum of 3 previous |↵
| LIS | LIS ending at index i | `max(dp[o]+1)` for s[o]<s[i] |↵
| Grid | best sum to reach cell (i,j) | `max(top, left) + val` |↵
| Dice | ways to make sum i | sum over 6 dice faces |↵
↵
↵
