1D DP — Climbing Stairs to House Robber

1D DP — Climbing Stairs to House Robber

Dynamic programming (DP) solves a problem by combining answers to smaller versions of the same problem, computing each smaller answer only once. In 1-D DP, the smaller versions are prefixes of the input ("the first i steps", "the first i houses", "the first i characters"), so the answers fit in a one-dimensional array dp[i].

Every 1-D DP solution comes from answering four questions:

1. State: what exactly does dp[i] mean? Write it down in words.
2. Transition: how is dp[i] built from earlier entries? Think about the last decision made.
3. Base cases: the smallest inputs, answered directly.
4. Answer: which entry (or combination of entries) is the final result?

Climbing Stairs: counting ways

• State: dp[i] = the number of ways to reach step i.
• Last decision: the final move onto step i was a 1-step (from i−1) or a 2-step (from i−2). These are different ways, so add them: dp[i] = dp[i−1] + dp[i−2].
• Base: dp[0] = 1 (one way to stand at the start), dp[1] = 1.

int climbStairs(int n) {
    int prev2 = 1, prev1 = 1;                   // dp[0], dp[1]
    for (int i = 2; i <= n; i++) {
        int cur = prev1 + prev2;
        prev2 = prev1;
        prev1 = cur;
    }
    return prev1;
}

Only the last two values are needed, so the array collapses to two variables: O(n) time, O(1) space. (It's the Fibonacci sequence.) The naive recursion ways(n) = ways(n−1) + ways(n−2) without memoization recomputes the same subproblems exponentially many times, about 1.6ⁿ calls. That's the waste DP removes.

Variation, allowed steps {1, 3, 5}: dp[i] = dp[i−1] + dp[i−3] + dp[i−5] (skipping negative indexes). The structure is identical; only the list of "last moves" changes.

Min Cost Climbing Stairs: optimizing instead of counting

int minCostClimbingStairs(int[] cost) {
    int a = 0, b = 0;                              // min cost to stand on "step i-2" and "step i-1" (before paying)
    for (int i = 2; i <= cost.length; i++) {
        int cur = Math.min(b + cost[i - 1], a + cost[i - 2]);
        a = b;
        b = cur;
    }
    return b;
}

Counting problems add over the choices. Optimization problems take the min or max over them. The recurrence shape is the same.

House Robber: take it or skip it

• State: dp[i] = the best total using the first i houses.
• Last decision: for house i−1, either skip it (dp[i−1]) or rob it, which means the previous house must be skipped (dp[i−2] + nums[i−1]).

int rob(int[] nums) {
    int skipPrev = 0, best = 0;                    // dp[i-2], dp[i-1]
    for (int x : nums) {
        int cur = Math.max(best, skipPrev + x);
        skipPrev = best;
        best = cur;
    }
    return best;
}

Greedy fails here. Picking the largest house first on [2, 3, 2] or [5, 1, 1, 5] goes wrong, because one choice constrains its neighbours. That constraint between neighbouring choices is the signal that you need DP.

House Robber II (houses in a circle): the first and last houses are now adjacent. Run the linear version twice, once excluding the first house and once excluding the last, and take the maximum.

Decode Ways: validity conditions on each choice

The last decision is "the final letter used 1 digit, or 2 digits". Each option is only allowed when its digits form a valid code:

int numDecodings(String s) {
    int n = s.length();
    int[] dp = new int[n + 1];
    dp[0] = 1;                                              // empty string: one (empty) decoding
    for (int i = 1; i <= n; i++) {
        if (s.charAt(i - 1) != '0') dp[i] += dp[i - 1];     // single digit 1..9
        if (i >= 2) {
            int two = (s.charAt(i - 2) - '0') * 10 + (s.charAt(i - 1) - '0');
            if (two >= 10 && two <= 26) dp[i] += dp[i - 2]; // two digits 10..26 (no leading zero)
        }
    }
    return dp[n];
}

Zeros are the trap. "0" alone decodes to nothing, "06" isn't valid, and "100" has 0 decodings.

Coin Change: the transition looks back by variable amounts

• State: dp[a] = the fewest coins to make amount a.
• Last decision: the last coin used was some c, so dp[a] = 1 + min over coins c ≤ a of dp[a − c].

int coinChange(int[] coins, int amount) {
    int[] dp = new int[amount + 1];
    Arrays.fill(dp, amount + 1);                   // "infinity": more coins than could ever be needed
    dp[0] = 0;
    for (int a = 1; a <= amount; a++)
        for (int c : coins)
            if (c <= a) dp[a] = Math.min(dp[a], dp[a - c] + 1);
    return dp[amount] > amount ? -1 : dp[amount];
}

O(amount × number of coins). Using amount + 1 as infinity avoids the overflow you'd get from Integer.MAX_VALUE + 1. Greedy ("largest coin first") fails for coins like {1, 3, 4} and amount 6 (greedy gives 4+1+1, but the optimum is 3+3). Counting the number of combinations instead ("Coin Change II") loops over coins in the outer loop, so that each combination is counted once regardless of order.

Word Break: "is there a valid last piece?"

boolean wordBreak(String s, List<String> words) {
    Set<String> dict = new HashSet<>(words);
    int maxLen = words.stream().mapToInt(String::length).max().orElse(0);
    boolean[] dp = new boolean[s.length() + 1];
    dp[0] = true;                                           // empty prefix is always segmentable
    for (int i = 1; i <= s.length(); i++)
        for (int j = Math.max(0, i - maxLen); j < i && !dp[i]; j++)   // only check plausible last-word lengths
            dp[i] = dp[j] && dict.contains(s.substring(j, i));
    return dp[s.length()];
}

dp[i] asks, "does the prefix of length i split into words?" It does if some shorter segmentable prefix is followed by a dictionary word. Limiting j by the longest word length is a simple, effective optimization.

Patterns that look like DP but have a simpler answer

• Jump Game (can you reach the end?) is solvable by DP, but a greedy scan tracking the farthest reachable index is O(n) and O(1).
• Maximum subarray (Kadane's algorithm) is a 1-D DP where best ending at i = max(nums[i], best ending at i−1 + nums[i]). For the maximum product subarray, keep both the max and the min ending at i, because a negative number swaps them.

Follow-up questions this topic invites — and their answers

Q: Top-down memoization or bottom-up tabulation? A: Both have the same complexity. Top-down (recursion plus a cache) follows the recurrence directly and only computes the states it actually needs. Bottom-up avoids recursion depth limits and makes space optimization (keeping only the last few values) easy. In interviews, deriving top-down first and then converting is a good approach.

Q: How do you know a problem needs DP rather than greedy? A: When a locally best choice can block a better global result, such as adjacent houses or coin denominations where the largest coin first fails. Try to find a small counterexample to the greedy rule. If you find one, and subproblems overlap, use DP.

Q: When can you reduce the space to O(1)? A: When dp[i] depends only on a fixed number of previous entries (like i−1 and i−2). Keep just those in variables. It isn't possible when the transition can reach arbitrarily far back (Coin Change, Word Break).

Q: Why initialize Coin Change with amount + 1 rather than Integer.MAX_VALUE? A: Because the code computes dp[a − c] + 1, and MAX_VALUE + 1 overflows to a negative number, corrupting the minimum. Any value larger than the maximum possible answer (at most amount coins of value 1) works as infinity.

Q: How do you reconstruct the actual choice, such as which houses to rob? A: Keep the full dp array (not just two variables) and walk backwards. At each i, check which option produced dp[i] (skip or take) and step back accordingly, recording the "take" decisions.