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

Source: https://skills101.in/learn/dsa/dsa-dp-1d-patterns — Skills101 free tutorial (Data Structures & Algorithms). Updated 2026-11-21.

**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).

```python
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)])
```

```text
[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])`.

```python
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
```

```text
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](https://skills101.in/learn-img/dsa/coin-change.svg)

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.)

```python
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))
```

```text
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.

```java
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));
    }
}
```

```text
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](https://skills101.in/learn-img/dsa/lis.svg)

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.

```python
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))
```

```text
(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 quiz and free certificate: https://skills101.in/learn/dsa/dsa-dp-1d-patterns