1D DP

1. Introduction

What is 1D DP?

1D DP represents dynamic programming problems where the subproblem states can be described using a single-variable index, e.g., dp[i] represents the optimal solution for elements from index 0 up to i.

Why study them?

1D DP is the most frequent starting point for DP interview questions. Mastering 1D recurrence patterns is key to understanding state transition formulas, base cases, and tabulation space optimization.

Where is it Used?

Financial Investment Planning: Allocating asset capital weights over linear time steps.

Resource Allocation: Scheduling tasks with adjacent exclusion constraints.

---

2. Mental Models

House Robber: Take-or-Skip Decision

Imagine walking down a street of houses with a loot bag:

At each house i, you have a binary choice:

- Rob house i: You get nums[i] loot, but you cannot rob house i-1. Thus, your maximum loot is nums[i] + max_loot_up_to(i-2). - Skip house i: You don't rob it, so your maximum loot is identical to max_loot_up_to(i-1).

You take the maximum of these two choices: dp[i] = max(dp[i-1], dp[i-2] + nums[i]).

---

3. Core Algorithms & Implementations

1. House Robber (LeetCode 198)

State: dp[i] = max money robbed from houses 0 to i.

Recurrence: dp[i] = max(dp[i-1], dp[i-2] + nums[i]).

2. Coin Change (LeetCode 322)

State: dp[amount] = min coins to make amount.

Recurrence: dp[a] = min(dp[a], 1 + dp[a - c]) for each coin c where c <= a.

---

4. Visualizing Subproblem Overlaps: House Robber

For houses [2, 7, 9, 3]:

When resolving rob(3), the subproblem rob(1) is requested twice (by Rob3 and Skip2). Storing this result in a cache avoids redundant calculations.

---

5. Real-World Examples

Server Load Balancing: Selecting CPU scheduling blocks to maximize throughput while avoiding adjacent resource conflicts.

Vending Machines: Identifying the fewest bills/coins required to return a customer's change balance.

---

6. Interview Perspective

How Interviewers Ask This Topic

Interviewers test optimization progressions:

"Given houses, find maximum loot." -> Solve using dp[i] = max(dp[i-1], dp[i-2] + nums[i]). Explain how to optimize space complexity from O(N) to O(1) by using two variables (prev1 and prev2) instead of a full DP array.

"Why initialize the Coin Change table with amount + 1 instead of Integer.MAX_VALUE?" -> Because adding 1 to Integer.MAX_VALUE (e.g. 1 + dp[a-c]) will cause integer overflow, flipping to negative bounds and causing incorrect results.

Common Mistakes

> 2. Wrong Coin Change Base Case: Forgetting to set dp[0] = 0. If dp[0] is initialized to infinity, all derived amounts will also remain infinite.

---

7. Summary

Recurrence Formulation: Define dp[i] clearly. Connect it to smaller indexes (i-1, i-2).

Top-Down (Memoization): Recursive, lazy validation.

Bottom-Up (Tabulation): Iterative loop, stack-safe. Space-optimize from O(N) to O(1) when transitions only depend on adjacent variables.

---

8. Quiz

Question 1: What is the recurrence equation for Climbing Stairs (making steps of size 1 or 2)?

Answer: dp[i] = dp[i-1] + dp[i-2], identical to the Fibonacci recurrence equation.

Question 2: How do you space-optimize the Coin Change tabulation table?

Answer: You cannot easily optimize Coin Change space to O(1) because the transition depends on coin values, which are arbitrary variables. Thus, we must maintain the full table of size amount + 1.

Question 3: If target is 6 and coins are [3, 4], what is the output of coinChange?

Answer: -1 (impossible to make change). The final value in the table at index 6 remains infinite.

Question 4: True or False: Tabulation is always faster than Memoization.

Answer: False. Although Tabulation avoids recursion stack frame overhead, Memoization can be faster if only a small fraction of subproblem states need to be computed (lazy evaluation).

Question 5: What occurs if you execute Top-Down Memoization on N = 10^5 without adjustments?

Answer: It will likely trigger a Stack Overflow error due to the deep recursive call stack, whereas Bottom-Up tabulation will run cleanly.