More DP Adventures — Coins and Stairs

Real-world analogy

What is it?

This lesson covers classic DP problems that appear frequently in programming contests and interviews. The climbing stairs problem and coin change problem are the perfect next step after Fibonacci — they use the same DP thinking but in more practical scenarios. Mastering these patterns gives you the foundation to solve hundreds of DP variations.

Real-world relevance

The coin change algorithm is used by vending machines to figure out the best way to give you change with the fewest coins. The stairs problem is similar to path planning — like figuring out how many different routes a robot can take on a grid. Delivery companies use DP to find the cheapest shipping routes, and game designers use DP to calculate all possible move combinations.

Key points

• The Climbing Stairs Problem — You are at the bottom of a staircase with N steps. Each time, you can climb 1 or 2 steps. How many distinct ways can you reach the top? For 1 step, there is 1 way. For 2 steps, there are 2 ways (1+1 or 2). For 3 steps, there are 3 ways. The pattern is exactly Fibonacci! dp[i] = dp[i-1] + dp[i-2] because you either came from one step below (took 1 step) or two steps below (took 2 steps).
• Extending Stairs — What if You Can Take 1, 2, or 3 Steps? — If you can take 1, 2, or 3 steps at a time, the recurrence becomes dp[i] = dp[i-1] + dp[i-2] + dp[i-3]. The idea is the same — you could have arrived from 1, 2, or 3 steps below. This is called the Tribonacci variant. See how easy it is to extend DP once you understand the pattern? Just add more terms to the recurrence!
• The Coin Change Problem — Minimum Coins — You have coins of certain values (like 1, 5, and 10 cents) and you need to make exactly N cents using the fewest coins possible. For example, to make 13 cents with coins {1, 5, 10}, the answer is 4 coins (10+1+1+1). dp[i] represents the minimum coins needed to make amount i. For each coin value c, dp[i] = min(dp[i], dp[i-c] + 1). Start with dp[0] = 0 (zero coins for zero amount).
• The Coin Change Problem — Count Ways — A different coin problem: how many WAYS can you make N cents? For example, making 5 cents with {1, 2, 5} has 4 ways: 5, 2+2+1, 2+1+1+1, and 1+1+1+1+1. This time dp[i] counts the number of ways. We loop through coins and for each coin c, add dp[i-c] to dp[i]. This is a classic interview and contest problem!
• How to Identify DP Problems — Here are the biggest hints: the problem asks for minimum, maximum, or count. You can make choices that affect future options. The problem has optimal substructure — the best solution to the big problem uses the best solutions to smaller problems. Greedy does not work (like always taking the biggest coin does not always give minimum coins). If you see these signs, try DP!
• Setting Up the DP Table — Always start by asking: what does dp[i] represent? For stairs, dp[i] = number of ways to reach step i. For coin change, dp[i] = minimum coins to make amount i. Then ask: what are the base cases? dp[0] is usually 0 or 1. Finally ask: how does dp[i] depend on smaller values? Write that relationship and you have your solution!
• Handling Impossible Cases — Sometimes there is no solution — like making 3 cents with only {2, 4} coins. You need to handle this! A common trick is to initialize dp[] with a very large number (like 1e9 or INT_MAX) meaning 'impossible.' Only dp[0] starts at 0. If dp[N] is still huge at the end, then there is no valid solution. Always remember to check for impossible cases in your output!
• Practice Tips for DP — Start with these classic problems in order: Fibonacci, Climbing Stairs, Coin Change (min coins), Coin Change (count ways), and House Robber. These five problems teach you the core DP patterns. After you understand them, move to 2D DP problems like grid paths and knapsack. Practice 2-3 DP problems per week and you will become comfortable within a month!

Code example

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

// ===== Problem 1: Climbing Stairs =====
// How many ways to climb N stairs (1 or 2 steps at a time)?
long long climbStairs(int n) {
    if (n <= 2) return n;
    
    vector<long long> dp(n + 1);
    dp[1] = 1;  // 1 way to climb 1 stair
    dp[2] = 2;  // 2 ways to climb 2 stairs (1+1 or 2)
    
    for (int i = 3; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];  // Come from 1 or 2 steps below
    }
    return dp[n];
}

// ===== Problem 2: Minimum Coins =====
// Find the fewest coins needed to make amount N
int minCoins(vector<int>& coins, int amount) {
    vector<int> dp(amount + 1, 1e9);  // Initialize with "impossible"
    dp[0] = 0;  // 0 coins needed for amount 0
    
    for (int i = 1; i <= amount; i++) {
        for (int c : coins) {
            if (c <= i && dp[i - c] != 1e9) {
                dp[i] = min(dp[i], dp[i - c] + 1);
            }
        }
    }
    return dp[amount] == 1e9 ? -1 : dp[amount];  // -1 if impossible
}

// ===== Problem 3: Count Ways to Make Change =====
// How many ways can you make amount N using given coins?
long long countWays(vector<int>& coins, int amount) {
    vector<long long> dp(amount + 1, 0);
    dp[0] = 1;  // 1 way to make amount 0: use no coins
    
    for (int c : coins) {             // Loop coins in outer loop!
        for (int i = c; i <= amount; i++) {
            dp[i] += dp[i - c];       // Add ways using this coin
        }
    }
    return dp[amount];
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    // Climbing Stairs
    int n = 10;
    cout << "Ways to climb " << n << " stairs: " << climbStairs(n) << "\n";
    
    // Minimum Coins
    vector<int> coins = {1, 5, 10, 25};
    int amount = 37;
    cout << "Min coins for " << amount << " cents: " << minCoins(coins, amount) << "\n";
    
    // Count Ways
    cout << "Ways to make " << amount << " cents: " << countWays(coins, amount) << "\n";
    
    return 0;
}

Line-by-line walkthrough

1. 1. climbStairs(n) uses a DP array where dp[i] = number of ways to reach step i. We know dp[1] = 1 (just take one step) and dp[2] = 2 (take 1+1 or take 2). Everything else builds from these.
2. 2. The loop for (int i = 3; i <= n; i++) fills the table bottom-up. dp[i] = dp[i-1] + dp[i-2] because you either took 1 step from stair i-1 or 2 steps from stair i-2. Same as Fibonacci!
3. 3. minCoins() initializes dp[] with 1e9 (a huge number representing 'impossible'). Only dp[0] = 0 because you need 0 coins to make 0 cents.
4. 4. For each amount i from 1 to N, we try every coin c. If coin c is not bigger than i and dp[i-c] is not impossible, then dp[i] = min(dp[i], dp[i-c] + 1). The +1 is for using one more coin of value c.
5. 5. If dp[amount] is still 1e9 at the end, it means no combination of coins can make that amount, so we return -1.
6. 6. countWays() is different — the outer loop goes over coins, not amounts! This is important. Looping coins outside prevents counting the same combination in different orders (like 1+5 and 5+1 as separate ways).
7. 7. For each coin c, we update dp[i] += dp[i-c] for all valid amounts. This means: the number of ways to make amount i increases by the number of ways to make (i minus this coin).
8. 8. dp[0] = 1 in countWays because there is exactly 1 way to make amount 0: use no coins at all. This base case is crucial — without it, all values would stay 0.
9. 9. In main(), we test all three functions. Climbing 10 stairs gives 89 ways. Making 37 cents with {1,5,10,25} takes 4 coins (25+10+1+1). These are classic results you should memorize!

Spot the bug

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

int minCoins(vector<int>& coins, int amount) {
    vector<int> dp(amount + 1, 1e9);
    dp[0] = 0;
    
    for (int i = 1; i <= amount; i++) {
        for (int c : coins) {
            if (c <= i) {
                dp[i] = min(dp[i], dp[i - c] + 1);
            }
        }
    }
    return dp[amount];
}

int main() {
    vector<int> coins = {3, 7};
    cout << minCoins(coins, 5) << "\n";  // Should say impossible!
    return 0;
}

Explain like I'm 5

Fun fact

Hands-on challenge

More resources

• Climbing Stairs — NeetCode (YouTube — NeetCode)
• Coin Change — LeetCode 322 (LeetCode)
• Introduction to DP — Codeforces Blog (Codeforces)