DP Basics¶
In one sentence
If the answer to a big question can be built from answers to smaller versions of the same question, compute each small answer once, store it, and build upward. That is dynamic programming (DP).
1. What problem does it solve?¶
Example — AtCoder EDU DP A · Frog 1
There are \(n\) stones with heights \(h_1, \dots, h_n\). A frog starts on stone \(1\). From stone \(i\) it can jump to \(i + 1\) or \(i + 2\), and a jump from \(i\) to \(j\) costs \(|h_i - h_j|\). Find the minimum total cost to reach stone \(n\).
Limits: \(n \le 10^5\).
Input Output
4
10 30 40 20 30
Path \(1 \to 2 \to 4\): \(|10 - 30| + |30 - 20| = 20 + 10 = 30\).
Brute force tries every sequence of \(+1\)/\(+2\) jumps. The number of ways to reach stone \(n\) is a Fibonacci number, about \(1.6^n\): for \(n = 100\) that is \(10^{20}\) paths.
But the paths share a lot. Every path to stone \(4\) arrives from stone \(3\) or stone \(2\). If we already know the cheapest cost to reach stone \(3\) and to reach stone \(2\), we do not care how they were reached. Only those two numbers matter.
2. The math¶
2.1 The five questions of every DP¶
| question | Frog 1 |
|---|---|
| State: what does one number mean? | \(dp_i\) = minimum cost to reach stone \(i\) |
| Transition: how is it built from smaller states? | \(dp_i = \min\big(dp_{i-1} + \lvert h_i - h_{i-1} \rvert,\;\; dp_{i-2} + \lvert h_i - h_{i-2} \rvert\big)\) |
| Base case: what needs no transition? | \(dp_1 = 0\) (we start there) |
| Order: which states must be ready first? | increasing \(i\), since \(dp_i\) needs \(dp_{i-1}\) and \(dp_{i-2}\) |
| Answer: which state do we print? | \(dp_n\) |
Why the transition is right. Every path to stone \(i\) makes its last jump either from \(i - 1\) or from \(i - 2\). In the first case, the rest of the path is a path to \(i - 1\), and the cheapest one costs \(dp_{i-1}\). The second case is the same with \(i - 2\). The best path to \(i\) is the better of the two cases.
2.2 Filling the table¶
\(h = [10, 30, 40, 20]\):
| \(i\) | \(h_i\) | from \(i-1\) | from \(i-2\) | \(dp_i\) |
|---|---|---|---|---|
| 1 | 10 | — | — | 0 |
| 2 | 30 | \(0 + 20 = 20\) | — | 20 |
| 3 | 40 | \(20 + 10 = 30\) | \(0 + 30 = 30\) | 30 |
| 4 | 20 | \(30 + 20 = 50\) | \(20 + 10 = 30\) | 30 |
\(n\) states, \(O(1)\) work each: \(O(n)\) instead of \(1.6^n\).
2.3 Counting instead of minimising¶
The same structure counts ways. For "how many ways to climb \(n\) stairs taking 1 or 2 steps", the last step was either \(1\) (from \(n - 1\)) or \(2\) (from \(n - 2\)), and those two groups of ways never overlap:
For a minimum we take \(\min\) over the cases; for a count we add them; for "is it possible" we take \(\text{or}\).
2.4 Two ways to write it¶
| style | how | pros | cons |
|---|---|---|---|
| bottom-up (tabulation) | loop over states in order and fill a list | fast, no recursion limit | you must figure out the order |
| top-down (memoization) | recursive function; save each result the first time and return the saved value later | follows the recursive idea directly | Python recursion limit and overhead |
Both compute each state once. The saving comes from never recomputing, not from the style.
3. Lesson code¶
3.1 Bottom-up: counting stairs (June 21)¶
def solve():
n = int(input())
dp = [0] * (n + 1)
dp[0] = 1
for i in range(1, n + 1):
dp[i] = dp[i - 1] + (dp[i - 2] if i - 2 >= 0 else 0)
# dp[i] tells the result for a sub-problem
# how many plans we can use to reach the i-th level
# dynamic programming
print(dp[n])
3.2 Top-down: memoized recursion (June 21)¶
This is our lesson code for 1498C · Planar Reflections (8-dp-1 · C). state[m][k] stores the answer for "a particle of age \(k\) with \(m\) planes in front of it", and \(0\) means "not computed yet".
def solve():
n, k = map(int, input().split())
state = [[0] * (k + 1) for _ in range(n + 1)]
def dfs(m, k):
if k == 1 or m == 0:
return 1
if state[m][k] == 0:
state[m][k] = (dfs(m - 1, k) + dfs(n - m, k - 1)) % MOD
return state[m][k]
print(dfs(n, k))
Why this got Memory Limit Exceeded
The recursion can go about \(n + k\) calls deep, and every test case allocates a new \((n + 1) \times (k + 1)\) table. With many test cases in Python, both cost memory. The fix is to write the same recurrence bottom-up (§2.4).
4. Worked solution — Frog 1¶
The table from §2.2 as code. Index \(0\) is stone \(1\).
import sys
input = sys.stdin.readline
def solve():
n = int(input())
h = list(map(int, input().split()))
dp = [0] * n
for i in range(1, n):
dp[i] = dp[i - 1] + abs(h[i] - h[i - 1])
if i >= 2:
dp[i] = min(dp[i], dp[i - 2] + abs(h[i] - h[i - 2]))
print(dp[n - 1])
solve()
5. Worked solution — Basketball Exercise¶
1195C · Basketball Exercise (8-dp-1 · B, rating 1400)
Two rows of \(n\) students stand side by side; the heights are \(h_{1,1..n}\) and \(h_{2,1..n}\). Choose students from left to right (each chosen index strictly larger than the previous one) so that no two consecutive chosen students come from the same row. Maximise the total height.
Limits: \(n \le 10^5\), heights \(\le 10^9\).
Input Output
5
9 3 5 7 3
5 8 1 4 5 29
3
1 2 9
10 1 1 19
1
7
4 7
State. What matters for the future is only which row the last chosen student came from. So keep two numbers after looking at the first \(i\) columns:
- \(A_i\) = best total whose last chosen student is from row 1 (or nobody chosen yet),
- \(B_i\) = best total whose last chosen student is from row 2 (or nobody chosen yet).
Transition. At column \(i\) we can skip both students, or take one of them:
Taking row 1's student is allowed only after a row-2 student (or at the start, where \(B = 0\)), which is exactly \(B_{i-1} + h_{1,i}\). The answer is \(\max(A_n, B_n)\).
Trace the first sample:
| column \(i\) | \(h_{1,i}\) | \(h_{2,i}\) | \(A_i = \max(A, B + h_1)\) | \(B_i = \max(B, A + h_2)\) |
|---|---|---|---|---|
| start | 0 | 0 | ||
| 1 | 9 | 5 | \(\max(0, 0 + 9) = 9\) | \(\max(0, 0 + 5) = 5\) |
| 2 | 3 | 8 | \(\max(9, 5 + 3) = 9\) | \(\max(5, 9 + 8) = 17\) |
| 3 | 5 | 1 | \(\max(9, 17 + 5) = 22\) | \(\max(17, 9 + 1) = 17\) |
| 4 | 7 | 4 | \(\max(22, 17 + 7) = 24\) | \(\max(17, 22 + 4) = 26\) |
| 5 | 3 | 5 | \(\max(24, 26 + 3) = 29\) | \(\max(26, 24 + 5) = 29\) |
Answer \(29\) (for example \(9, 8, 5, 4, 3\) from rows \(1, 2, 1, 2, 1\)).
import sys
input = sys.stdin.readline
def solve():
n = int(input())
h1 = list(map(int, input().split()))
h2 = list(map(int, input().split()))
A = 0
B = 0
for i in range(n):
new_A = max(A, B + h1[i])
new_B = max(B, A + h2[i])
A = new_A
B = new_B
print(max(A, B))
solve()
Update both from the old values
A = max(A, B + h1[i]) followed by B = max(B, A + h2[i]) would use the new A, which may already include column \(i\), and take both students of the same column. Compute new_A and new_B first.
6. Common mistakes¶
State that does not capture enough
If \(dp_i\) forgets something the future depends on, the transition becomes wrong. In Basketball Exercise, "best total after \(i\) columns" alone is not enough; you must also know the row of the last student. The same holds for EDU DP C · Vacation.
Wrong or missing base case
Counting problems need \(dp_0 = 1\) (one way to do nothing). With \(dp_0 = 0\) every count becomes \(0\).
Reading a state before it is computed
Loop in the order the transition needs. Top-down never has this problem, but it pays in recursion.
Using 0 as \"not computed\" when 0 is a real answer
The memo in §3.2 is safe because every answer is at least \(1\). If \(0\) can be an answer, initialise with -1 or use a dict.
Forgetting the modulo
Counts grow exponentially. Apply % MOD at every addition, not only at the end, or Python's big integers make everything slow.
7. Practice¶
| Problem | Set | Rating | Idea |
|---|---|---|---|
| EDU DP A · Frog 1 | AtCoder (June 28) | — | this page |
| 1195C · Basketball Exercise | 8-dp-1 · B | 1400 | this page |
| EDU DP B · Frog 2 | AtCoder (June 28) | — | jumps up to \(K\): \(K\) cases |
| EDU DP C · Vacation | AtCoder (June 28) | — | state = (day, activity) |
| 1743C · Save the Magazines | 8-dp-1 · A | 1100 | state = (box, whether the lid moved) |
| 1498C · Planar Reflections | 8-dp-1 · C | 1600 | the memo in §3.2, written bottom-up |
| EDU DP H · Grid 1 | AtCoder (July 5) | — | 2D state, see LCS |
Next: Knapsack, where the state has two parts, item and capacity.
Credits & licenses
- The "five questions" framing: follows USACO Guide — Introduction to DP by Michael Cao, Benjamin Qi, Neo Wang and Daniel Zhu, licensed CC BY-NC-SA 4.0.
- §3 is our lesson code. Everything else (tables, proofs, worked solutions, mistakes) is ours.