1-D DP
Plan a route of jobs in a notebook, one line per day. Each line holds the best total so far, so tomorrow’s choice only looks at the last two lines. The final line is the answer, built without ever redoing a day.
2 · Watch
No sound? Captions are on by default.
3 · Now you drive
Keys:←→ stepSpace playR reset
House Robber
or try
1–8 amounts from 0 to 99, one per house, separated by spaces.dp[i] is the most you can take from the first i houses. With none, it’s 0.Step 1 of 11. 5 houses. dp[0] = 0. The rest of the row is empty.
Step 1 of 11
solution.ts▶ marks the line running now
function rob(nums: number[]): number {
const dp: number[] = new Array(nums.length + 1).fill(0);
dp[1] = nums[0];
for (let i = 2; i <= nums.length; i++) {
const skip = dp[i - 1];
const take = dp[i - 2] + nums[i - 1];
dp[i] = Math.max(skip, take);
}
return dp[nums.length];
}
4 · Your turn
0 of 10 problems solved
- Easy01
Climbing Stairs
Warm-up: each step adds the two ways below it.
- Medium02
House Robber
The one you just watched. Write it from memory.
- Medium03
House Robber II
Same street, but the ends are neighbours too.
- Medium04
Longest Palindromic Substring
Grow the answer out from each centre.
- Medium05
Palindromic Substrings
Count the palindromes around every centre.
- Medium06
Decode Ways
Each digit stands alone or pairs with its neighbour.
- Medium07
Coin Change
Fewest coins per amount, built coin by coin.
- Medium08
Maximum Product Subarray
Track the best and worst ending at each step.
- Medium09
Word Break
Each cut asks whether the prefix already breaks.
- Medium10
Longest Increasing Subsequence
Each number extends the best run before it.