Skills101

AdvancedData Structures & Algorithms · Lesson 33 of 40 · Updated ·

1D Dynamic Programming Patterns — Climbing Stairs, House Robber, Coin Change and LIS

Dynamic programming (DP) solves a big problem by combining answers to smaller versions of the same problem, and stores each smaller answer so it is computed only once. The earlier DP lesson showed the idea with Fibonacci. This lesson works through the four one-dimensional problems that appear again and again in placement tests, using one recipe every time.

1. The recipe

For every DP problem, write down four things before coding:

  1. State: what does dp[i] mean, in words? (This is the hardest and most important step.)
  2. Recurrence: how is dp[i] built from smaller states?
  3. Base case: the smallest states whose answers you know directly.
  4. Answer: which state (or which max/min over states) is the final answer?

In 1D problems the state is a single number: a position in an array, an amount of money, a step number.

2. Climbing stairs

Problem: you climb n steps, taking 1 or 2 steps at a time. How many different ways are there to reach the top?

  • State: dp[i] = number of ways to reach step i.
  • Recurrence: the last move was either 1 step (from i − 1) or 2 steps (from i − 2), so dp[i] = dp[i − 1] + dp[i − 2].
  • Base: dp[0] = 1 (one way: do nothing), dp[1] = 1.

dp[i] only needs the previous two values, so we can keep two variables instead of a whole array. This space optimisation turns O(n) memory into O(1).

def climb(n):
    a, b = 1, 1             # dp[0], dp[1]
    for _ in range(2, n + 1):
        a, b = b, a + b
    return b

print([climb(n) for n in range(1, 8)])
[1, 2, 3, 5, 8, 13, 21]

The numbers are Fibonacci numbers — the same recurrence in a different story.

3. House robber

Problem: houses in a row hold some money. You cannot rob two adjacent houses (the alarm rings). What is the most you can collect?

  • State: dp[i] = the most money from the first i + 1 houses (houses 0..i).
  • Recurrence: for house i, either skip it (dp[i − 1]) or rob it, which means house i − 1 is skipped (dp[i − 2] + money[i]). Take the larger.
  • Base: dp[0] = money[0], dp[1] = max(money[0], money[1]).
def rob(money):
    prev2, prev1 = 0, 0          # best up to i-2 and up to i-1
    for m in money:
        prev2, prev1 = prev1, max(prev1, prev2 + m)
    return prev1

print(rob([2, 7, 9, 3, 1]))      # 2 + 9 + 1
print(rob([5, 1, 1, 5]))         # 5 + 5
12
10

The second example shows why a greedy "take every other house" fails: houses 0 and 3 are the best pair, and they are three apart.

4. Coin change

Problem A (fewest coins): coins of given values, unlimited supply of each. What is the fewest number of coins that make amount? Return −1 if impossible.

  • State: dp[x] = fewest coins that make exactly x.
  • Recurrence: the last coin is some c ≤ x, so dp[x] = 1 + min(dp[x − c]) over all coins.
  • Base: dp[0] = 0; everything else starts at infinity ("not reachable yet").

Coin change with coins 1, 3, 4: dp from 0 to 6 is 0 1 2 1 1 2 2, so 6 needs 2 coins (3 + 3), while greedy picks 4 + 1 + 1 = 3 coins

The picture shows why we need DP here: the greedy rule "take the biggest coin first" gives 4 + 1 + 1 (3 coins), but 3 + 3 uses only 2. (For Indian currency notes greedy happens to work, but not for every coin system.)

def min_coins(coins, amount):
    INF = float('inf')
    dp = [0] + [INF] * amount
    for x in range(1, amount + 1):
        for c in coins:
            if c <= x and dp[x - c] + 1 < dp[x]:
                dp[x] = dp[x - c] + 1
    return dp[amount] if dp[amount] != INF else -1

print(min_coins([1, 3, 4], 6), min_coins([2], 3), min_coins([1, 2, 5], 11))
2 -1 3

Problem B (number of ways): how many different combinations of coins make amount? Here order does not matter (1 + 2 and 2 + 1 are the same way). Put the coin loop outside: each coin is added to the table in turn, so every combination is counted in one fixed coin order.

public class Main {
    static long countWays(int[] coins, int amount) {
        long[] ways = new long[amount + 1];
        ways[0] = 1;                          // one way to make 0: no coins
        for (int c : coins)                   // coin loop OUTSIDE = combinations
            for (int x = c; x <= amount; x++)
                ways[x] += ways[x - c];
        return ways[amount];
    }

    public static void main(String[] args) {
        System.out.println(countWays(new int[]{1, 2, 5}, 5));
        System.out.println(countWays(new int[]{2}, 3));
        System.out.println(countWays(new int[]{1, 2, 5, 10}, 20));
    }
}
4
0
40

For amount 5 the four ways are 5, 2+2+1, 2+1+1+1 and 1+1+1+1+1. If you swap the loops (amount outside, coins inside), you count ordered sequences instead — that is the "combination sum IV" problem, a different question.

5. Longest increasing subsequence (LIS)

A subsequence keeps the original order but may skip elements. Problem: the length of the longest strictly increasing subsequence.

  • State: dp[i] = length of the longest increasing subsequence that ends at index i.
  • Recurrence: dp[i] = 1 + max(dp[j]) over all j < i with a[j] < a[i] (or 1 if there is no such j).
  • Answer: max(dp) — the best subsequence can end anywhere.

LIS of 10 9 2 5 3 7 101 18: dp is 1 1 1 2 2 3 4 4, so the answer is 4, for example 2, 3, 7, 101

This is O(n²). A faster O(n log n) method keeps a list tails, where tails[k] is the smallest possible last value of an increasing subsequence of length k + 1. For each number, binary-search the first tail that is ≥ it and replace that tail (or append if none). The length of tails is the answer. tails is not itself a valid subsequence; only its length is meaningful.

from bisect import bisect_left

def lis_n2(a):
    dp = [1] * len(a)
    for i in range(len(a)):
        for j in range(i):
            if a[j] < a[i]:
                dp[i] = max(dp[i], dp[j] + 1)
    return max(dp), dp

def lis_fast(a):
    tails = []
    for x in a:
        k = bisect_left(tails, x)
        if k == len(tails):
            tails.append(x)
        else:
            tails[k] = x
    return len(tails), tails

a = [10, 9, 2, 5, 3, 7, 101, 18]
print(lis_n2(a))
print(lis_fast(a))
(4, [1, 1, 1, 2, 2, 3, 4, 4])
(4, [2, 3, 7, 18])

6. How to spot 1D DP

The problem says…Likely state
"number of ways to reach step / position n"dp[i] = ways to reach i
"maximum / minimum total, with a rule about neighbours"dp[i] = best using items 0..i
"fewest items to make a total"dp[x] = best for total x
"longest subsequence with a property"dp[i] = best ending at i

The common signal: a choice at each step (take or skip, which coin, which previous element), and choices that overlap — the same smaller question is asked many times.

Common mistakes

  • Starting to code before writing the state in words. Most wrong DP answers come from a vague state.
  • Forgetting the base case dp[0] = 0 (coin change) or ways[0] = 1 (counting ways).
  • Mixing up combinations and ordered sequences by putting the loops in the wrong order.
  • Using max(dp) vs dp[n − 1] wrongly: LIS needs max(dp); house robber's dp[n − 1] is already the best.
  • Treating the tails list in the fast LIS as the actual subsequence.

Quick recap

  • Recipe: state in words, recurrence, base case, answer.
  • Climbing stairs: dp[i] = dp[i−1] + dp[i−2]; house robber: max(skip, rob); both need only two variables.
  • Coin change: fewest coins dp[x] = 1 + min(dp[x − c]); number of ways with the coin loop outside.
  • LIS: dp[i] ends at i, O(n²); patience-style tails with binary search gives O(n log n).

Practice what you learned

📝 Quiz: 1D Dynamic Programming Patterns5 questions · instant answers & explanations · +10 XP · counts towards your free certificateTake the quiz →