Dynamic Programming for Beginners: From Recursion to a DP Table

Dynamic programming (DP) has a reputation for being the hardest topic for beginners. A lot of that comes from the name, which says nothing about what it does. The real idea is simple: if a problem breaks into smaller versions of itself, and those smaller versions repeat, solve each one once and store the answer.

This post builds up DP with two classic problems, the frog and coin change, and gives a checklist you can reuse.

Problem 1: the frog

There are n stones in a row with heights h₁, …, h_n. A frog starts on stone 1 and wants to reach stone n. From stone i it can jump to i + 1 or i + 2, and a jump costs the absolute difference in height. What is the minimum total cost? This is AtCoder DP Contest A – Frog 1.

Step 1: define the state

Let dp[i] = the minimum cost to reach stone i. Choosing what dp[i] means is the most important decision in any DP. A good state is small and captures everything the future depends on. Here, once the frog is on stone i, it does not matter how it got there.

Step 2: write the transition

The frog reaches stone i either from stone i − 1 or from stone i − 2. So:

dp[i] = min( dp[i-1] + |h[i] - h[i-1]|,
             dp[i-2] + |h[i] - h[i-2]| )

Step 3: base case and order

The cost to reach the first stone is 0, since the frog starts there. Every dp[i] only uses smaller indices, so we fill the table from left to right. (The code below numbers stones from 0, as C++ arrays do.)

Why not plain recursion?

You could write the formula as a recursive function. But computing dp[i] calls dp[i − 1] and dp[i − 2], each of which calls two more, and the number of calls grows like the Fibonacci numbers, which is exponential. The same values get recomputed again and again. Storing each answer the first time (either with memoization or with a table like below) makes it linear.

Code (C++)

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> h(n);
    for (auto &x : h) cin >> x;

    // dp[i] = minimum cost to reach stone i
    vector<long long> dp(n, LLONG_MAX);
    dp[0] = 0;
    for (int i = 1; i < n; i++) {
        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]));
    }
    cout << dp[n - 1] << '\n';
    return 0;
}

For heights 10 30 40 20, the best path is 1 → 2 → 4 with cost 20 + 10 = 30. The table is dp = [0, 20, 30, 30].

Complexity: O(n) time and memory.

Problem 2: fewest coins

You have coin values c₁, …, c_n, with unlimited coins of each. What is the fewest number of coins that add up to exactly x? Print −1 if it is impossible. This is CSES 1634 – Minimizing Coins.

Greedy (always take the largest coin) fails here. With coins 1, 5 and 7 and x = 10, greedy takes 7 + 1 + 1 + 1 = 4 coins, but 5 + 5 uses only 2.

• State: dp[s] = fewest coins that sum to exactly s.
• Transition: the last coin used is some c, so dp[s] = min over coins of dp[s − c] + 1.
• Base case: dp[0] = 0, and every other value starts as “impossible”.

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, x;
    cin >> n >> x;
    vector<int> c(n);
    for (auto &v : c) cin >> v;

    const int INF = 1e9;
    // dp[s] = fewest coins that add up to exactly s
    vector<int> dp(x + 1, INF);
    dp[0] = 0;
    for (int s = 1; s <= x; s++)
        for (int coin : c)
            if (coin <= s && dp[s - coin] != INF)
                dp[s] = min(dp[s], dp[s - coin] + 1);

    cout << (dp[x] == INF ? -1 : dp[x]) << '\n';
    return 0;
}

Complexity: O(n · x) time and O(x) memory.

A checklist for any DP problem

1. State: what does dp[…] mean, in one sentence?
2. Transition: what was the last decision, and how does it connect to smaller states?
3. Base cases: which states can you answer directly?
4. Order: in which order must states be filled so that dependencies are ready?
5. Answer: which state, or combination of states, is the final answer?

If you can answer all five in plain words before coding, the code is usually short.

Practice problems

• AtCoder DP A – Frog 1, then B (the frog can jump up to k stones).
• CSES 1633 – Dice Combinations: count the ways instead of minimising.
• CSES 1634 – Minimizing Coins: the coin problem above.