Current state depends on 1–2 prior states (Fibonacci, stairs)
House Robber: dp[i] = max(dp[i-1], dp[i-2] + nums[i])
Coin Change: dp[j] = min over all coins of dp[j-coin]+1
Decode Ways: dp[i] based on 1-digit and 2-digit checks
Product subarray: track both min and max (negatives flip sign)
💡 Space optimization: if dp[i] only needs dp[i-1] and dp[i-2], replace the array with two variables prev1 and prev2.
⚡ Complexity
Time
O(n)
Space
O(1)*
*Space-optimized with prev1/prev2 variables instead of full dp array. Coin Change uses O(amount) array since it needs all prior values.
Live Animation · 1D Linear DP · LC #198
Problem
Given nums = [2,7,9,3,1] representing money in each house, find the maximum amount you can rob without robbing two adjacent houses. Transition: dp[i] = max(dp[i-1], dp[i-2] + nums[i]) — either skip this house or rob it plus the best 2 steps back.
Input: nums = [2, 7, 9, 3, 1] · Answer: 12 (rob houses 0+2+4 = 2+9+1)
Step 0 / 5
nums[] — house values
dp[] — max rob up to index i
prev2
0
prev1
0
curr
—
answer
—
Press ▶ Play or Next ▶ to begin the House Robber animation.
int prev2 = 0, prev1 = 0;
Step 0 / 6
dp[0..6] — min coins to make amount j | coins = [1, 3, 5], amount = 6
amount j
—
best coin
—
dp[j]
—
Press ▶ Play or Next ▶ to begin the Coin Change animation.
Arrays.fill(dp, amount + 1); dp[0] = 0;
Java Pattern Templatesskeleton only
// ─── 1D DP: House Robber (space-optimized) ───────────────int prev2 = 0, prev1 = 0;
for (int num : nums) {
int curr = Math.max(prev1, prev2 + num); // rob or skip
prev2 = prev1;
prev1 = curr;
}
return prev1;
// ─── Coin Change (unbounded knapsack) ────────────────────int[] dp = new int[amount + 1];
Arrays.fill(dp, amount + 1); // sentinel "infinity"
dp[0] = 0;
for (int j = 1; j <= amount; j++)
for (int coin : coins)
if (coin <= j)
dp[j] = Math.min(dp[j], dp[j - coin] + 1);
return dp[amount] > amount ? -1 : dp[amount];
// ─── Decode Ways (conditional 1-digit / 2-digit) ─────────int prev2 = 1, prev1 = s.charAt(0) != '0' ? 1 : 0;
for (int i = 2; i <= n; i++) {
int curr = 0;
int one = Integer.parseInt(s.substring(i-1, i));
int two = Integer.parseInt(s.substring(i-2, i));
if (one >= 1) curr += prev1; // valid 1-digitif (two >= 10 && two <= 26) curr += prev2; // valid 2-digit
prev2 = prev1; prev1 = curr;
}
return prev1;