"The friendliest DPs have a single number as their state — usually an index. dp[i] is 'the best answer considering everything up to position i,' built from a couple of earlier entries. Once you see that shape, a whole family of problems becomes routine."
One-Dimensional State
A 1D DP is one whose subproblem is identified by a single number — typically an index into an array, or a remaining amount. You define dp[i] as the answer to the subproblem 'considering the first i elements' (or 'making amount i'), and you express it in terms of a few earlier dp values. The whole solution is then a single loop filling the array left to right. Climbing stairs, coin change, and house robber are all 1D DPs — the state is just 'how far along am I?'
House Robber: a Clean Recurrence
The classic: a row of houses with values; you can't rob two adjacent houses; maximize the loot. The insight is a per-house choice — for house i, either you skip it (so your best is whatever dp[i-1] was) or you rob it (so your best is nums[i] plus dp[i-2], since i-1 must then be skipped). So dp[i] = max(dp[i-1], dp[i-2] + nums[i]). That single line captures the entire problem, and since it depends only on the previous two entries, it space-optimizes to two variables. Most 1D DPs have exactly this flavor: a short recurrence relating dp[i] to a handful of earlier cells.
A 1D DP indexes its state by a single number (usually an array position). Define dp[i] as the best answer up to i, written as a short recurrence over a few earlier entries — e.g. house robber's dp[i] = max(dp[i-1], dp[i-2] + nums[i]). Fill left to right; space-optimize to a few variables.
Kadane's Algorithm: the Gem
The most elegant 1D DP is Kadane's algorithm for the maximum-sum contiguous subarray. The state: best_ending_here = the largest subarray sum that ends at the current position. At each element you make one choice — extend the previous run (best_ending_here + x) or start fresh from here (x), whichever is larger — and track the best you've seen. It's O(n), O(1) space, and a single pass. "Best ending here" is a thinking pattern worth memorizing: many array DPs are cracked by defining the state as 'the best solution that ends exactly at index i,' then taking the max over all i.
Pippa's Confession
Maximum subarray stumped me — I was checking all O(n²) subarrays. Dad gave me one phrase: "best ending here." Instead of all subarrays, track only the best one ending at the current spot, and either extend it or restart. Suddenly it was one pass, O(n). That 'best ending here' reframing has unlocked more array DPs for me than any other single idea — it turns 'consider all subarrays' into 'make one local choice per element.'
Code
House robber and Kadane's algorithm·python
# HOUSE ROBBER: max loot, no two adjacent houses. dp[i] from dp[i-1], dp[i-2].
def rob(nums):
prev2, prev1 = 0, 0 # dp[i-2], dp[i-1] (space-optimized)
for x in nums:
# skip house (prev1) OR rob it (x + prev2)
prev2, prev1 = prev1, max(prev1, prev2 + x)
return prev1
print(rob([2, 7, 9, 3, 1])) # 12 (rob houses 2, 9, 1)
# KADANE'S: maximum-sum contiguous subarray, O(n), 'best ending here'.
def max_subarray(nums):
best_ending_here = best_overall = nums[0]
for x in nums[1:]:
# extend the previous run, or start fresh at x — whichever is bigger
best_ending_here = max(x, best_ending_here + x)
best_overall = max(best_overall, best_ending_here)
return best_overall
print(max_subarray([-2, 1, -3, 4, -1, 2, 1, -5, 4])) # 6 (the run [4,-1,2,1])
# Brute force checks all O(n^2) subarrays; Kadane makes ONE choice per element -> O(n).
Hand-trace house robber on [2, 7, 9, 3, 1], computing dp[i] = max(dp[i-1], dp[i-2] + nums[i]) at each step. What's the final answer and which houses are robbed? Then explain why the recurrence only needs the previous TWO dp values, and how that enables O(1) space.
Hint
dp: 2, 7, max(7,2+9)=11, max(11,7+3)=11, max(11,11+1)=12 → answer 12 (houses with values 2, 9, 1). It needs only dp[i-1] and dp[i-2] because robbing i forbids i-1 but allows i-2; since nothing older is referenced, two rolling variables suffice → O(1) space.
Progress
Progress is local-only — sign in to sync across devices.