Introduction to Dynamic Programming (Intro to DP) - Preparation to IOI Part 2
Introduction to Dynamic Programming (Intro to DP)
Introduction to Dynamic Programming (Intro to DP)
Introduction
Dynamic programming, or DP, is a way to solve a problem by solving smaller cases first and then combining their answers to get bigger answers. Instead of trying the same work many times, we store useful answers in a table and reuse them later. In simple words, DP is recursion with memory, but we usually write it as filling an array or table from known values to the final answer.
A state is one smaller subproblem whose answer we want to know. For example, in the frog problem, dpi means the minimum cost needed to reach stone i. A transition is the rule that computes one state from earlier states. For example, if we know the best costs for stones i−1 and , we can compute the best cost for stone .
i
−
2
i
Every DP also needs base states and a final state. Base states are the easiest states where the answer is already known, like dp1=0 because the frog starts on stone 1. The final state is the state that answers the original problem, like dpn in this problem.
Usually, when solving dynamic programming problems, we follow this logic: first come up with DP states and understand how to break the problem into smaller subproblems. Then determine the base states, just like in recursion, where some answers are known in advance. After that, come up with transitions, meaning how to compute each state using simpler subproblems.
Problem Statement
Suppose a frog stands on stone 1 and wants to reach stone n. There are n stones in a line, and stone i has height hi. From stone i, the frog can jump to stone i+1 or stone i+2. The cost of jumping from stone i to stone j is ∣hi−hj∣. Find the minimum total cost needed to reach stone n.
Example: if h=[10,30,40,20], one good path is 1→2→4, with total cost ∣10−30∣+∣30−20∣=30. The task looks simple, but if we try all possible jump paths, their number grows very fast.
Brute force solution
The first idea is to solve the problem recursively. To reach stone i, the frog could come from stone i−1 or from stone i−2. So we try both possibilities and take the smaller cost.
Detailed recursion trace for brute(5)
C++
source · C++line 1
1long long brute(int i) {
2 if (i == 1) {
3 return 0;
4 }
5 long long res = brute(i - 1) + abs(h[i] - h[i - 1]);
We start from the final stone and want to compute brute(5).
Each node is one separate entrance into brute(i)directed
activequeuedvisitedScroll to zoom · drag to pan
call stack
1brute(5)
entered Calls1returned Calls0base Case Calls0
L1
01 / 65
This is correct because the last jump to stone i must be from one of the previous two stones. The problem is that the same values are recomputed many times. For example, while solving stone 6, we may solve stone 4 from different recursive branches again and again, so this solution becomes too slow.
Efficient solution and algorithm
Bottom-up DP: compute each state once
C++
source · C++line 1
1dp[1] = 0;
2if (n >= 2) {
3 dp[2] = abs(h[2] - h[1]);
4}
5for (int i = 3; i <= n; i++) {
6 long long x = dp[i - 1] + abs(h[i] - h[i - 1]);
7 long long y = dp[i - 2] + abs(h[i] - h[i - 2]);
8 dp[i] = min(x, y);
9}
10cout << dp[n] << '\n';
Set dp[1]
L1
The frog starts on stone 1, so dp[1] = 0.
inv
To compute dp[i], we only use dp[i - 1] and dp[i - 2].
heights h[1..5]5 cells
10
30
40
20
25
0
1
2
3
4
stone 1
dp[1..5]5 cells
0
?
?
?
?
0
1
2
3
4
dp[1]
Stones and possible jumpsdirected
activequeuedvisitedScroll to zoom · drag to pan
candidate costs
Map
dp[1]
0
computed States1complexityO(n)
L1
01 / 11
The improvement is to store answers for smaller stones and reuse them. Let dpi be the minimum cost needed to reach stone i. If we already know dpi−1 and dpi−2, then we can compute dpi directly.
This value dpi is called a state. A state is one smaller subproblem whose answer we want to know. In this problem, the state dpi asks a very clear question: what is the minimum cost to reach stone i?
Some states are known immediately. These are called base states. Here, dp1=0, because the frog starts on stone 1 and does not need to pay anything to be there. If n≥2, then dp2=∣h2−h1∣, because there is only one way to reach stone 2.
A transition is the rule that computes a state using simpler states. To reach stone i, the last jump has only two possible forms. If the frog comes from stone i−1, the total cost is dpi−1+∣hi−hi−1∣. If the frog comes from stone i−2, the total cost is dpi−2+∣hi−hi−2∣. We choose the smaller one, so for i≥3 we get dpi=min(dpi−1+∣.
This is dynamic programming. We split the problem into smaller states, determine the base states, and then use transitions to compute all other states.
Algorithm:
Recap for solving DP problems:
Come up with DP states. This means understanding how to break the problem into smaller subproblems.
Determine base states. Just like in recursion, we need to know for which states the answer is already known.
Come up with transitions. This means deciding how to compute each state using simpler subproblems.
In this problem, the state is dpi, the base states are dp1=0 and optionally dp2=∣h2−h1∣, and the transition takes the best option from stone i−1 or stone i−2. The algorithm is fast because every dpi is computed exactly once. We no longer try all paths; we only keep the best answer for each stone.
Implementation
Complexity
Time:O(n) — each stone is processed once.
Memory:O(n) — we store one DP value for each stone.
hi
−
hi−1∣,dpi−2+
∣hi−
hi−2∣)
1. Read n and the heights h[1], h[2], ..., h[n].
2. Let dp[i] mean the minimum cost to reach stone i.
3. Set dp[1] = 0.
4. If n >= 2, set dp[2] = abs(h[2] - h[1]).
5. For each i from 3 to n:
1. Let x = dp[i - 1] + abs(h[i] - h[i - 1]).
2. Let y = dp[i - 2] + abs(h[i] - h[i - 2]).
3. Set dp[i] = min(x, y).
6. Output dp[n].
#include <bits/stdc++.h>using namespace std;const int N = 200005;int n;long long h[N];long long dp[N];int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); cin >> n; for(int i = 1; i <= n; i++){ cin >> h[i];} dp[1] = 0; if(n >= 2){ dp[2] = abs(h[2] - h[1]);} for(int i = 3; i <= n; i++){ long long x = dp[i - 1] + abs(h[i] - h[i - 1]); long long y = dp[i - 2] + abs(h[i] - h[i - 2]); dp[i] = min(x, y);} cout << dp[n]<< '\n'; return 0;}