Chapter 3: 1D DP Patterns
Pattern recognition: When you see a linear sequence and need to make a decision at each index, think 1D DP. The state is usually indexed by position i, and the recurrence compares a few neighboring states.
House Robber
You are a robber planning a heist on a street of houses. Each house nums[i] holds a non-negative amount of money. Adjacent houses share a security system — rob two neighbors and the alarm triggers. Maximize loot without robbing adjacent houses.
Example: nums = [2, 7, 9, 3, 1] → answer 12 (rob houses 0, 2, and 4: 2 + 9 + 1).
Derive the formula
Walk through the 5-step framework. Each step builds on the last until you have a complete recurrence.
You walk down a street of houses, each with a non-negative loot value. You cannot rob two adjacent houses. What does dp[i] represent?
Visualize the table
Step through the DP table cell by cell. Notice how each cell only depends on the two cells to its left — that is what makes space optimization possible.
dp[2] = max(dp[1], dp[0] + nums[2]) = max(7, 2 + 9) = max(7, 11) = 11
Aha: House Robber is Fibonacci with a twist. Instead of adding, you take a max at each step. The constraint "no adjacent" forces you to look back two positions when you choose to rob.
Code
Longest Increasing Subsequence
Given an integer array, return the length of the longest strictly increasing subsequence. A subsequence keeps relative order but skips elements freely.
Example: nums = [10, 9, 2, 5, 3, 7, 101, 18] → answer 4 (e.g. [2, 3, 7, 18]).
Derive the formula
The critical choice is how you define the subproblem. "LIS up to index i" does not work — you need to know where the subsequence ends.
Given an integer array, find the length of the longest strictly increasing subsequence. What does dp[i] represent?
Aha: The subproblem definition matters — "ending at i" vs "up to i" changes everything. With "up to i", you lose track of which elements are available to extend, and the recurrence breaks down.
Press play or step forward to see the recurrence in action.
Code
The O(n²) DP checks every pair (j, i) with j < i. There is an O(n log n) patience-sorting approach, but the DP version is the one to master first.
Maximum Subarray (Kadane's Algorithm)
Find the contiguous subarray with the largest sum. This is classic 1D DP where dp[i] = max sum of a subarray ending at index i.
Recurrence: dp[i] = max(dp[i-1] + nums[i], nums[i]) — either extend the previous subarray or start fresh at i. The answer is max(dp[i]) over all i.
Example: nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4] → answer 6 (subarray [4, -1, 2, 1]).
dp[1] = max(dp[0] + nums[1], nums[1]) = max(-2 + 1, 1) = max(-1, 1) = 1
Coin Change
Given coin denominations and a target amount, return the fewest coins needed to make that amount, or -1 if impossible. This is the unbounded knapsack flavor of 1D DP — each coin can be reused.
Subproblem: dp[i] = minimum coins to make amount i.
Recurrence: dp[i] = min(dp[i - coin] + 1) over all coins where i - coin >= 0.
Example: coins = [1, 3, 4], amount = 6 → answer 2 (3 + 3).
dp[1] = min(dp[0]+1=1) = 1 (use coin 1)
Tips for 1D DP
Space optimization: When only the last 1–2 values are needed (House Robber, Fibonacci, Kadane), replace the array with two variables. If you need the full last row (Coin Change), you can often still use a 1D array and iterate amounts left to right.
Complexity pattern: 1D DP usually runs in O(n) time when each cell depends on O(1) neighbors, or O(n²) when each cell scans all previous indices (LIS). Space is O(n) for the table, O(1) after optimization when applicable.
Watch out: Always clarify whether your state means "ending at i" or "considering up to i." Mixing these definitions is the most common source of wrong recurrences in 1D DP.