Pattern 27 of 27
1D Dynamic Programming
Break a problem into a sequence of overlapping subproblems where each answer depends on a few earlier ones, and fill them in order.
- Cost
- O(n) time for fixed transitions, O(n · k) when each state tries k choices
- Problems
- 6
When to reach for it
- The prompt asks for a maximum, a minimum, or a number of ways.
- A choice at step i only depends on results for earlier steps.
- Plain recursion recomputes the same smaller inputs many times.
How it works
Start by defining the state precisely, for example "the best total using the first i houses", then write the recurrence from the last decision: rob house i and add the best total up to i - 2, or skip it and keep the best up to i - 1. Base cases come from the smallest inputs. Because each state only reads a fixed number of earlier states, the table often shrinks to two variables. Coin Change and Perfect Squares instead try every choice inside each state.
The template
Written for House Robber (write-up)
def rob(nums):
skip, take = 0, 0 # best two houses back, best one house back
for x in nums:
skip, take = take, max(take, skip + x)
return takeSix problems, in learning order
- 1.Climbing StairsLeetCode 70Ways to reach step i are the ways to reach i - 1 plus the ways to reach i - 2.Easy
- 2.House RobberLeetCode 198Take or skip each house.Medium
- 3.House Robber IILeetCode 213A circular street: run House Robber twice, once without the first house and once without the last.Medium
- 4.Coin ChangeLeetCode 322dp[amount] is one plus the best dp[amount - coin]; unreachable amounts stay infinite.Medium
- 5.Perfect SquaresLeetCode 279The Coin Change shape, with square numbers as the coins.Not in the curated 370 yet.Medium
- 6.Longest Increasing SubsequenceLeetCode 300dp[i] is the longest run ending at i; patience sorting brings it to O(n log n).Medium
What usually goes wrong
- Defining the state loosely, so the recurrence does not actually hold.
- Wrong base cases, especially an amount of 0 in Coin Change.
- Using a greedy rule where DP is required, such as always taking the largest coin.
1D Dynamic Programming, answered
When should I use the 1d dynamic programming pattern?
The prompt asks for a maximum, a minimum, or a number of ways. A choice at step i only depends on results for earlier steps. Plain recursion recomputes the same smaller inputs many times.
What is the time complexity of 1d dynamic programming?
O(n) time for fixed transitions, O(n · k) when each state tries k choices. Coin Change and Perfect Squares instead try every choice inside each state.
Which problem should I start with for 1d dynamic programming?
Start with Climbing Stairs (LeetCode 70, Easy). Ways to reach step i are the ways to reach i - 1 plus the ways to reach i - 2. The six problems on this page are in learning order.