Chapter 61 of 65

1D Dynamic Programming

In the previous chapter, we learned the core idea of Dynamic Programming: solve each subproblem once, store the answer, and reuse it.

Now it's time to practise that idea on real problems.

The simplest family of DP problems is 1D Dynamic Programming. In these problems, the state can be described by just one number, usually an index or an amount, so the DP table is a single array:

dp[0]  dp[1]  dp[2]  dp[3]  ...  dp[n]

1D DP is dynamic programming where each state depends on a single variable, so all answers fit in a one-dimensional array dp[i].

Many famous interview problems are 1D DP: Climbing Stairs, House Robber, Coin Change, Longest Increasing Subsequence, and Maximum Subarray. We'll solve each one using the five steps from the previous chapter:

State → Recurrence → Base cases → Order → Answer

Problem 1: Climbing Stairs

You are climbing a staircase with n steps. Each time you can climb 1 step or 2 steps. In how many different ways can you reach the top?

For n = 3, there are 3 ways:

1 + 1 + 1
1 + 2
2 + 1

Think About the Last Move

How did you arrive at step i? There are only two possibilities:

From step i - 1, by taking 1 step
From step i - 2, by taking 2 steps

So the number of ways to reach step i is the ways to reach i - 1 plus the ways to reach i - 2.

The DP Formulation

State      : dp[i] = number of ways to reach step i
Recurrence : dp[i] = dp[i - 1] + dp[i - 2]
Base cases : dp[0] = 1   (one way to stand at the ground: do nothing)
             dp[1] = 1   (only one way: a single 1-step)
Order      : i from 2 to n
Answer     : dp[n]

Filling the table for n = 5:

i     :  0   1   2   3   4   5
dp[i] :  1   1   2   3   5   8

Does that look familiar? It is the Fibonacci sequence, shifted by one position. Many DP problems turn out to be Fibonacci in disguise.

static long climbStairs(int n) {

    if (n <= 1) {
        return 1;
    }

    long[] dp = new long[n + 1];
    dp[0] = 1;
    dp[1] = 1;

    for (int i = 2; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }

    return dp[n];
}

climbStairs(5) returns 8.

Complexity: Time O(n), Space O(n). Since each value uses only the previous two, it can be reduced to O(1) space exactly like Fibonacci.


Problem 2: Min Cost Climbing Stairs

Now each step has a cost. cost[i] is what you pay when you step on stair i. After paying, you may climb 1 or 2 steps. You may start at stair 0 or stair 1 for free, and the "top" is just past the last stair (index n).

Example:

cost = [10, 15, 20]

Best: start at stair 1, pay 15, jump 2 steps to the top.
Answer: 15

The DP Formulation

State      : dp[i] = minimum cost to reach position i
Recurrence : dp[i] = min(dp[i - 1] + cost[i - 1],
                         dp[i - 2] + cost[i - 2])
Base cases : dp[0] = 0, dp[1] = 0   (starting is free)
Answer     : dp[n]

The idea is the same as before: to reach position i, your last move came from i - 1 (paying cost[i - 1]) or from i - 2 (paying cost[i - 2]). This time we take the minimum instead of the sum.

cost  = [10, 15, 20]

dp[0] = 0
dp[1] = 0
dp[2] = min(dp[1] + 15, dp[0] + 10) = min(15, 10) = 10
dp[3] = min(dp[2] + 20, dp[1] + 15) = min(30, 15) = 15  ← answer
static int minCostClimbingStairs(int[] cost) {

    int n = cost.length;
    int[] dp = new int[n + 1];   // dp[0] = dp[1] = 0 by default

    for (int i = 2; i <= n; i++) {
        dp[i] = Math.min(dp[i - 1] + cost[i - 1],
                         dp[i - 2] + cost[i - 2]);
    }

    return dp[n];
}

Notice the pattern: "count the ways" problems usually add the choices, while "best answer" problems take the min or max of the choices.


Problem 3: House Robber

This is one of the most popular DP interview problems.

A robber wants to rob houses along a street. houses[i] is the money in house i. The only rule: you cannot rob two adjacent houses, because the alarm will go off. What is the maximum money you can rob?

houses = [2, 7, 9, 3, 1]

Rob houses 0, 2, 4 → 2 + 9 + 1 = 12
Answer: 12

Why Greedy Fails

A greedy idea like "always take the richest house available" doesn't work. For [2, 7, 9, 3, 1], it would pick 9, then 2 and 1, giving 12 here by luck. But for [5, 6, 5], it picks 6 and gets 6, while the best answer is 5 + 5 = 10.

We need to consider both choices at every house.

Take It or Skip It

At house i, you have two choices:

Skip house i  → best money stays dp[i - 1]
Rob house i   → you can't rob i - 1, so you get dp[i - 2] + houses[i]

We take whichever is larger.

The DP Formulation

State      : dp[i] = maximum money from houses 0..i
Recurrence : dp[i] = max(dp[i - 1], dp[i - 2] + houses[i])
Base cases : dp[0] = houses[0]
             dp[1] = max(houses[0], houses[1])
Answer     : dp[n - 1]

Trace for [2, 7, 9, 3, 1]:

i  houses[i]   dp[i]
0      2       2
1      7       max(2, 7)            = 7
2      9       max(7, 2 + 9)        = 11
3      3       max(11, 7 + 3)       = 11
4      1       max(11, 11 + 1)      = 12  ← answer
static int rob(int[] houses) {

    int n = houses.length;
    if (n == 0) {
        return 0;
    }
    if (n == 1) {
        return houses[0];
    }

    int[] dp = new int[n];
    dp[0] = houses[0];
    dp[1] = Math.max(houses[0], houses[1]);

    for (int i = 2; i < n; i++) {
        dp[i] = Math.max(dp[i - 1], dp[i - 2] + houses[i]);
    }

    return dp[n - 1];
}

Space-Optimized Version

Again, only the last two values are needed:

static int robOptimized(int[] houses) {

    int prev2 = 0;   // best up to house i - 2
    int prev1 = 0;   // best up to house i - 1

    for (int money : houses) {
        int current = Math.max(prev1, prev2 + money);
        prev2 = prev1;
        prev1 = current;
    }

    return prev1;
}

This version also handles an empty array naturally (it returns 0).

Complexity: Time O(n), Space O(1).


Problem 4: Coin Change (Minimum Coins)

In the previous chapter, we saw that greedy fails for coins {1, 3, 4} and amount 6. Now let's solve it properly.

Given coin denominations (you have an unlimited supply of each) and an amount, find the minimum number of coins needed to make that amount. If it's impossible, return -1.

Think About the Last Coin

To make amount a, the last coin you used was one of the coins. If it was coin, then before it you had made amount a - coin.

dp[a] = 1 + min(dp[a - coin])   for every coin ≤ a

The DP Formulation

State      : dp[a] = minimum coins needed to make amount a
Recurrence : dp[a] = min over all coins (dp[a - coin] + 1)
Base case  : dp[0] = 0   (zero coins make amount 0)
Others     : start as "infinity" (not reachable yet)
Order      : a from 1 to amount
Answer     : dp[amount], or -1 if it is still infinity

Table for coins {1, 3, 4}, amount 6:

a      :  0   1   2   3   4   5   6
dp[a]  :  0   1   2   1   1   2   2

dp[5] = min(dp[4] + 1, dp[2] + 1, dp[1] + 1) = min(2, 3, 2) = 2   (4 + 1)
dp[6] = min(dp[5] + 1, dp[3] + 1, dp[2] + 1) = min(3, 2, 3) = 2   (3 + 3)
static int coinChange(int[] coins, int amount) {

    int INF = amount + 1;            // more coins than could ever be needed
    int[] dp = new int[amount + 1];
    Arrays.fill(dp, INF);
    dp[0] = 0;

    for (int a = 1; a <= amount; a++) {
        for (int coin : coins) {
            if (coin <= a && dp[a - coin] != INF) {
                dp[a] = Math.min(dp[a], dp[a - coin] + 1);
            }
        }
    }

    return dp[amount] == INF ? -1 : dp[amount];
}

Why use amount + 1 as infinity instead of Integer.MAX_VALUE? Because Integer.MAX_VALUE + 1 overflows into a negative number, which would then win every min() and give a wrong answer. Since the answer can never need more than amount coins (even using only 1s), amount + 1 is a safe "impossible" value.

For coins {2} and amount 3, dp[3] stays infinity, so the answer is -1.

Complexity: Time O(amount × number of coins), Space O(amount).


Problem 5: Longest Increasing Subsequence (LIS)

A subsequence is formed by deleting zero or more elements without changing the order of the remaining ones. Elements don't have to be next to each other.

Find the length of the longest strictly increasing subsequence.

nums = [10, 9, 2, 5, 3, 7, 101, 18]

One LIS: 2, 3, 7, 101   (or 2, 5, 7, 18, etc.)
Answer: 4

The DP Formulation

This one needs a slightly different state. Instead of "best answer up to i", we use "best answer ending exactly at i":

State      : dp[i] = length of the longest increasing subsequence
                     that ENDS at index i
Recurrence : dp[i] = 1 + max(dp[j]) for all j < i with nums[j] < nums[i]
             (or just 1 if no such j exists)
Base case  : every dp[i] starts at 1 (the element alone)
Answer     : the MAXIMUM value in the whole dp array

Why "ending at i"? Because to extend a subsequence with nums[i], we must know its last element. Fixing the end makes that easy.

Trace:

index :  0   1   2   3   4   5    6    7
nums  : 10   9   2   5   3   7  101   18
dp    :  1   1   1   2   2   3    4    4

dp[3] = 2 → [2, 5]
dp[5] = 3 → [2, 5, 7] or [2, 3, 7]
dp[6] = 4 → [2, 5, 7, 101]
dp[7] = 4 → [2, 5, 7, 18]

Answer = max(dp) = 4
static int lengthOfLIS(int[] nums) {

    int n = nums.length;
    int[] dp = new int[n];
    Arrays.fill(dp, 1);
    int best = 0;

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < i; j++) {
            if (nums[j] < nums[i]) {
                dp[i] = Math.max(dp[i], dp[j] + 1);
            }
        }
        best = Math.max(best, dp[i]);
    }

    return best;
}

Notice that the answer is max(dp), not dp[n - 1]. The LIS doesn't have to end at the last element. This is a very common bug.

Complexity: Time O(n²) (each state looks at all earlier states), Space O(n).

There is also a faster O(n log n) method that keeps a list of the smallest possible "tail" for each length and updates it using binary search. It's a good follow-up to know for interviews, but the O(n²) DP is the one to understand first.


Problem 6: Maximum Subarray (Kadane's Algorithm)

Find the contiguous subarray with the largest sum.

nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]

Best subarray: [4, -1, 2, 1]
Answer: 6

Unlike LIS, a subarray must be contiguous (elements next to each other).

In the Divide and Conquer chapter, we solved this problem in O(n log n). With DP, we can do it in a single pass, in O(n).

The DP Formulation

State      : dp[i] = maximum sum of a subarray that ENDS at index i
Recurrence : dp[i] = max(nums[i], dp[i - 1] + nums[i])
Base case  : dp[0] = nums[0]
Answer     : max of all dp[i]

The recurrence asks a simple question at every index: "Should I extend the previous subarray, or start fresh from here?" If the previous best sum is negative, it only drags us down, so we start fresh.

i      :   0   1   2   3   4   5   6   7   8
nums   :  -2   1  -3   4  -1   2   1  -5   4
dp[i]  :  -2   1  -2   4   3   5   6   1   5
best   :  -2   1   1   4   4   5   6   6   6

Since dp[i] only depends on dp[i - 1], one variable is enough. This space-optimized DP is famously known as Kadane's Algorithm:

static int maxSubArray(int[] nums) {

    int current = nums[0];   // best sum ending here
    int best = nums[0];      // best sum seen so far

    for (int i = 1; i < nums.length; i++) {
        current = Math.max(nums[i], current + nums[i]);
        best = Math.max(best, current);
    }

    return best;
}

Starting with nums[0] (not 0) is important: if every number is negative, like [-3, -1, -2], the answer is -1, not 0.

Complexity: Time O(n), Space O(1).


Complete Java Program

Here are all six problems in one runnable program:

import java.util.Arrays;

class Main {

    // 1. Climbing Stairs
    static long climbStairs(int n) {
        if (n <= 1) {
            return 1;
        }
        long[] dp = new long[n + 1];
        dp[0] = 1;
        dp[1] = 1;
        for (int i = 2; i <= n; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp[n];
    }

    // 2. Min Cost Climbing Stairs
    static int minCostClimbingStairs(int[] cost) {
        int n = cost.length;
        int[] dp = new int[n + 1];
        dp[0] = 0;
        dp[1] = 0;
        for (int i = 2; i <= n; i++) {
            dp[i] = Math.min(dp[i - 1] + cost[i - 1],
                             dp[i - 2] + cost[i - 2]);
        }
        return dp[n];
    }

    // 3. House Robber
    static int rob(int[] houses) {
        int n = houses.length;
        if (n == 0) {
            return 0;
        }
        if (n == 1) {
            return houses[0];
        }
        int[] dp = new int[n];
        dp[0] = houses[0];
        dp[1] = Math.max(houses[0], houses[1]);
        for (int i = 2; i < n; i++) {
            dp[i] = Math.max(dp[i - 1], dp[i - 2] + houses[i]);
        }
        return dp[n - 1];
    }

    // 4. Coin Change (minimum coins)
    static int coinChange(int[] coins, int amount) {
        int INF = amount + 1;
        int[] dp = new int[amount + 1];
        Arrays.fill(dp, INF);
        dp[0] = 0;
        for (int a = 1; a <= amount; a++) {
            for (int coin : coins) {
                if (coin <= a && dp[a - coin] != INF) {
                    dp[a] = Math.min(dp[a], dp[a - coin] + 1);
                }
            }
        }
        return dp[amount] == INF ? -1 : dp[amount];
    }

    // 5. Longest Increasing Subsequence
    static int lengthOfLIS(int[] nums) {
        int n = nums.length;
        int[] dp = new int[n];
        Arrays.fill(dp, 1);
        int best = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[j] < nums[i]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
            best = Math.max(best, dp[i]);
        }
        return best;
    }

    // 6. Maximum Subarray (Kadane)
    static int maxSubArray(int[] nums) {
        int current = nums[0];
        int best = nums[0];
        for (int i = 1; i < nums.length; i++) {
            current = Math.max(nums[i], current + nums[i]);
            best = Math.max(best, current);
        }
        return best;
    }

    public static void main(String[] args) {

        System.out.println("Climbing stairs (n = 5)  : " + climbStairs(5));
        System.out.println("Climbing stairs (n = 45) : " + climbStairs(45));

        System.out.println("Min cost stairs          : "
            + minCostClimbingStairs(new int[]{10, 15, 20}));
        System.out.println("Min cost stairs          : "
            + minCostClimbingStairs(new int[]{1, 100, 1, 1, 1, 100, 1, 1, 100, 1}));

        System.out.println("House robber             : "
            + rob(new int[]{2, 7, 9, 3, 1}));

        System.out.println("Coin change {1,3,4} -> 6 : "
            + coinChange(new int[]{1, 3, 4}, 6));
        System.out.println("Coin change {2} -> 3     : "
            + coinChange(new int[]{2}, 3));

        System.out.println("LIS                      : "
            + lengthOfLIS(new int[]{10, 9, 2, 5, 3, 7, 101, 18}));

        System.out.println("Max subarray sum         : "
            + maxSubArray(new int[]{-2, 1, -3, 4, -1, 2, 1, -5, 4}));
    }
}

Output:

Climbing stairs (n = 5)  : 8
Climbing stairs (n = 45) : 1836311903
Min cost stairs          : 15
Min cost stairs          : 6
House robber             : 12
Coin change {1,3,4} -> 6 : 2
Coin change {2} -> 3     : -1
LIS                      : 4
Max subarray sum         : 6

The plain recursive version of climbStairs(45) would make billions of calls. The DP version does 44 additions.


Two Kinds of 1D States

If you look back, every problem used one of two state types:

State Type

Meaning

Final Answer

Problems

Prefix state

dp[i] = best answer using the first i items / steps

dp[n] or dp[n - 1]

Climbing Stairs, Min Cost Stairs, House Robber, Coin Change

Ending-at state

dp[i] = best answer that ends exactly at index i

max(dp[i]) over all i

LIS, Maximum Subarray

When the answer must "connect" to its last element (increasing order, contiguous subarray), use the ending-at state.


Space Optimization Summary

Problem

Depends On

Optimized Space

Climbing Stairs

dp[i-1], dp[i-2]

O(1)

Min Cost Stairs

dp[i-1], dp[i-2]

O(1)

House Robber

dp[i-1], dp[i-2]

O(1)

Maximum Subarray

dp[i-1]

O(1)

Coin Change

dp[a - coin] for any coin

O(amount) (can't shrink)

LIS

All earlier dp[j]

O(n) (can't shrink)

The rule: if a state depends on only a fixed number of previous states, you can keep just those in variables. If it can depend on any earlier state, you need the whole array.


Common Mistakes

1. Wrong base case for "count the ways"

In Climbing Stairs, dp[0] = 1, not 0. There is exactly one way to be at the start: do nothing. If you set it to 0, every count after it is wrong.

2. Returning dp[n - 1] for "ending-at" states

For LIS and Maximum Subarray, the best answer can end anywhere. Return the maximum over all indices.

3. Overflow with Integer.MAX_VALUE as infinity

Integer.MAX_VALUE + 1 becomes negative. Use a safe large value like amount + 1, or check for infinity before adding.

4. Forgetting edge cases

Empty arrays, a single element, an amount of 0, or all-negative numbers in Maximum Subarray. Always test these.

5. Confusing subarray and subsequence

A subarray is contiguous. A subsequence keeps order but can skip elements. They lead to completely different recurrences.


Practice Problems

Try these on LeetCode or GeeksforGeeks after this chapter. All of them are 1D DP:

  • Climbing Stairs (LeetCode 70)

  • Min Cost Climbing Stairs (LeetCode 746)

  • House Robber (LeetCode 198)

  • House Robber II, houses in a circle (LeetCode 213)

  • Coin Change (LeetCode 322)

  • Longest Increasing Subsequence (LeetCode 300)

  • Maximum Subarray (LeetCode 53)

  • Decode Ways (LeetCode 91)

  • Word Break (LeetCode 139)

  • Maximum Product Subarray (LeetCode 152)


The Main Idea

1D Dynamic Programming solves problems where the state is a single number, so the whole solution fits in one array dp[i].

The most useful trick for finding the recurrence is to ask: "What was the last choice?"

Climbing Stairs  → last move was 1 step or 2 steps
House Robber     → rob this house or skip it
Coin Change      → which coin was used last
LIS              → which earlier element comes just before this one
Maximum Subarray → extend the previous subarray or start fresh

Remember the two kinds of states:

Prefix state     → answer is dp[n]
Ending-at state  → answer is max(dp[i])

Define what dp[i] means, think about the last choice, combine the smaller answers with +, min, or max, and fill the array from left to right.

In the next chapter, we'll move to 2D Dynamic Programming, where the state needs two numbers, such as a row and a column in a grid.