1D Dynamic Programming Problems: Classic Patterns
Learn to solve common 1D dynamic programming problems including climbing stairs, house robber, and coin change with optimized space solutions.
1D Dynamic Programming Problems: Classic Patterns
1D DP problems use a single index to define subproblems. Despite their simplicity, they show up constantly in interviews and teach the core DP skills: state definition, recurrence formulation, and space optimization.
The key insight with 1D DP: the answer for position i depends only on some previous positions (usually i-1, i-2, or a range). Once you internalize the patterns, you can tackle any 1D DP problem systematically.
Introduction
One-dimensional DP problems use a single index to define subproblems, making them the gateway to dynamic programming mastery. Despite their relative simplicity compared to multi-dimensional DP, 1D problems appear constantly in interviews and teach the core skills that apply across all DP: state definition, recurrence formulation, base case handling, and space optimization. Once you internalize these patterns, tackling more complex DP becomes systematic rather than intimidating.
These problems appear everywhere—climbing stairs, house robber, coin change, longest increasing subsequence—because many optimization problems naturally reduce to “considering elements up to index i” where dp[i] represents the optimal solution for that prefix. The space optimization from O(n) to O(1) using rolling variables is often possible and demonstrates deeper understanding of the recurrence structure.
This guide works through classic 1D DP problems with full implementations: climbing stairs with variable step sizes, house robber with circular street constraint, coin change (both minimum coins and count of combinations), longest increasing subsequence (O(n²) DP and O(n log n) binary search variant), and word break. Each problem includes the recurrence derivation, base case explanation, and space optimization where applicable. Interview questions cover Kadane’s algorithm relationship to DP, loop order importance in combination problems, and greedy vs DP trade-offs.
Climbing Stairs
def climb_stairs(n):
"""Ways to reach nth stair (can take 1 or 2 steps). O(n) time, O(1) space."""
if n <= 2:
return n
prev2, prev1 = 1, 2 # dp[1]=1, dp[2]=2
for i in range(3, n + 1):
current = prev1 + prev2
prev2, prev1 = prev1, current
return prev1
def climb_stairs_with_variable_steps(n, steps):
"""
Generalization: can take 1, 2, or up to 'steps' steps.
dp[i] = sum(dp[i - step] for step in steps if i >= step)
"""
dp = [0] * (n + 1)
dp[0] = 1
for i in range(1, n + 1):
for step in steps:
if i >= step:
dp[i] += dp[i - step]
return dp[n]House Robber
def house_robber(nums):
"""
Max money robbed without robbing adjacent houses.
dp[i] = max(dp[i-1], dp[i-2] + nums[i])
"""
if not nums:
return 0
if len(nums) == 1:
return nums[0]
prev2, prev1 = nums[0], max(nums[0], nums[1])
for i in range(2, len(nums)):
current = max(prev1, prev2 + nums[i])
prev2, prev1 = prev1, current
return prev1
def house_robber_circular(nums):
"""Robber with circular street - can't rob first and last house."""
if not nums:
return 0
if len(nums) == 1:
return nums[0]
# Exclude last house or exclude first house
def rob_linear(houses):
prev2, prev1 = 0, 0
for money in houses:
current = max(prev1, prev2 + money)
prev2, prev1 = prev1, current
return prev1
return max(rob_linear(nums[:-1]), rob_linear(nums[1:]))Coin Change
def coin_change(coins, amount):
"""Min coins needed to make amount (unlimited coins)."""
dp = [float('inf')] * (amount + 1)
dp[0] = 0
for i in range(1, amount + 1):
for coin in coins:
if coin <= i:
dp[i] = min(dp[i], dp[i - coin] + 1)
return dp[amount] if dp[amount] != float('inf') else -1
def coin_change_ways(coins, amount):
"""Number of ways to make amount with unlimited coins."""
dp = [0] * (amount + 1)
dp[0] = 1
for coin in coins:
for i in range(coin, amount + 1):
dp[i] += dp[i - coin]
return dp[amount]Longest Increasing Subsequence (1D Variant)
def lis_length(nums):
"""Find LIS length - O(n²) DP, can be O(n log n) with binary search."""
if not nums:
return 0
n = len(nums)
dp = [1] * n # dp[i] = LIS length ending at index i
for i in range(1, n):
for j in range(i):
if nums[j] < nums[i]:
dp[i] = max(dp[i], dp[j] + 1)
return max(dp)
def lis_binary_search(nums):
"""O(n log n) LIS using patience sorting."""
import bisect
tails = []
for num in nums:
pos = bisect.bisect_left(tails, num)
if pos == len(tails):
tails.append(num)
else:
tails[pos] = num
return len(tails)Word Break
def word_break(s, word_dict):
"""Can string s be segmented into dictionary words?"""
word_set = set(word_dict)
n = len(s)
dp = [False] * (n + 1)
dp[0] = True
for i in range(1, n + 1):
for j in range(i):
if dp[j] and s[j:i] in word_set:
dp[i] = True
break
return dp[n]Common 1D DP Patterns
| Problem | Recurrence | Key Insight |
|---|---|---|
| Climb Stairs | dp[i] = dp[i-1] + dp[i-2] | Add current step to previous |
| House Robber | dp[i] = max(dp[i-1], dp[i-2] + nums[i]) | Take or skip current |
| Coin Change | dp[i] = min(dp[i], dp[i-coin] + 1) | Try each coin |
| LIS | dp[i] = max(dp[j] + 1) for j < i | Compare with smaller elements |
| Word Break | dp[i] = OR(dp[j] AND s[j:i] in dict) | Split at valid boundaries |
Space Optimization Patterns
# Full O(n) space
dp = [0] * (n + 1)
dp[i] = dp[i-1] + dp[i-2]
# Optimized to O(1)
prev2, prev1 = 0, 1 # corresponds to dp[-1], dp[0]
for i in range(1, n + 1):
current = prev1 + prev2
prev2, prev1 = prev1, currentWhen to Use 1D DP
Use 1D DP when:
- Problem can be expressed as “considering elements up to index i”
- Recurrence only depends on previous values (not the full history)
- You’re asked to optimize linear progression problems
Common interview triggers:
- “Maximum/Minimum subsequence…”
- “Ways to achieve…”
- “Can you partition/split…”
- “Longest increasing/decreasing…“
1D DP Trade-Offs
| Aspect | Top-Down (Memoized) | Bottom-Up (Tabulation) | Space-Optimized |
|---|---|---|---|
| Time | O(n) with memoization | O(n) | O(n) |
| Space | O(n) call stack + table | O(n) table | O(1) to O(k) |
| Debugging | Stack trace shows path | Full table for inspection | Harder to debug |
| Initialization | Lazy, compute on demand | Must init all states | Same as bottom-up |
| Recurrence access | Natural recursive | Must respect order | Must respect order |
Top-down: easier to write recursively, good when recurrence doesn’t need all subproblems. Bottom-up: explicit control over computation order, better for production. Space-optimized: use when recurrence only needs last k states, not the full history.
1D DP State Transition Flow
graph TD
START["Input Array"] --> INIT["Initialize dp array"]
INIT --> BASE["Set base cases\ndp[0], dp[1]"]
BASE --> LOOP["For i = 2 to n"]
LOOP --> TRANS["Apply recurrence:\ndp[i] = f(dp[i-1], dp[i-2], ...)"]
TRANS --> VALID{"Valid state?"}
VALID -->|"Yes"| STORE["Store dp[i]"]
STORE --> NEXT["i = i + 1"]
NEXT --> LOOP
VALID -->|"No"| ADJUST["Adjust recurrence\nor boundary conditions"]
ADJUST --> TRANS
LOOP -->|"i > n"| DONE["Return dp[n] or\noptimized result"]
DONE2["Space Optimization:\nKeep only needed previous states"]
STORE --> DONE2For 1D DP, each state represents the solution to a subproblem ending at that index. The recurrence tells you how to build dp[i] from earlier states.
Production Failure Scenarios and Mitigations
1D DP implementations break in specific ways once they hit production traffic.
O(n²) subproblem explosion
A poorly chosen recurrence can cause each state to re-compute the same subproblems multiple times. If your recurrence calls dp[i-1] and dp[i-2] without memoization in a naive recursive implementation, it effectively becomes exponential.
Fix: Use bottom-up tabulation with explicit state ordering. Verify your implementation’s time complexity matches theory by instrumenting subproblem counts.
Space optimization breaking when recurrence assumptions change
You implement space optimization keeping only the last two states because the recurrence only uses dp[i-1] and dp[i-2]. Then someone modifies the recurrence to use dp[i-3] for a new feature, and the optimized version silently produces wrong results.
Fix: Keep a full-table implementation in tests as a reference. When modifying recurrence relations, compare full-table output against optimized output for all test cases.
Integer overflow in DP with large values
DP for problems like “number of ways to climb 10⁹ stairs” produces astronomically large numbers that overflow 32-bit integers. In languages with fixed-size integers, this causes silent wraparound and wrong answers.
Fix: Use 64-bit integers or Python’s arbitrary-precision integers. For problems with large result values, store results modulo a prime but verify the modulo semantics match the problem requirements.
Off-by-one in base case setup
A dp array where dp[0] should represent an empty solution but gets initialized to 1 for the “one way to climb zero stairs” case. When combined with a recurrence that accesses dp[i-1], the off-by-one in base cases produces wrong results for larger inputs.
Fix: Write test cases for n=0, n=1, n=2, n=3 and verify against known results. Trace through by hand for n=3 to ensure base cases and recurrence interact correctly.
Quick Recap Checklist
- dp[i] represents answer for subproblem ending at index i
- Recurrence shows how dp[i] relates to smaller states
- Handle base cases (dp[0], dp[1]) correctly
- Consider space optimization when recurrence only uses limited previous states
- For O(n²) problems, check if O(n log n) alternatives exist
Observability Checklist
Track 1D DP implementations to catch performance and correctness issues early.
Core Metrics
- Subproblem count (should match theoretical complexity)
- DP array size and growth rate
- Time per subproblem computation
- Cache hit rate in recurrence lookups
- Memory footprint of DP table
Health Signals
- Subproblem count exceeding O(n) or O(n²) for expected input sizes
- DP table size growing faster than linear (possible state explosion)
- Execution time > expected by more than 2x
- Memory usage approaching limits for large n
Alerting Thresholds
- Subproblem count > 2x theoretical expectation: recurrence bug or attack
- DP table memory > 500MB for single problem: risk of OOM
- Execution time p99 > 1s for n < 10⁶: investigate
- Any silent overflow in result values: use larger type or modulo
Distributed Tracing
- Trace DP computation with subproblem count as span attribute
- Include n and recurrence depth in trace metadata
- Correlate slow DP runs with large input sizes or memory pressure
Security Notes
DP implementations have specific security concerns worth thinking about.
Algorithmic complexity attacks on DP recurrence
If user-controlled input affects the number or complexity of subproblems, an attacker can craft inputs that cause the DP to compute far more work than expected. A recurrence that’s O(n²) in the worst case gets weaponized against implementations assuming O(n) average case.
Fix: Set maximum input size thresholds for DP computations. Monitor subproblem counts and alert when actual computation exceeds expected by a large factor. Validate input ranges before starting DP.
Memoization table DoS via hash collision
If the memoization uses a hash table internally and the input keys are attacker-controlled, the attacker can craft keys that all hash to the same bucket, causing O(n²) lookup time instead of O(1).
Fix: Use language runtime-provided hash maps withDoS-resistant hash functions (like SipHash in Python’s dict). For cryptographic contexts, use constant-time comparison for memoized values.
Space complexity bombs causing OOM
A 1D DP problem where the recurrence unexpectedly requires O(n²) space (someone modified it to use a matrix instead of a vector) can exhaust memory.
Fix: Set hard limits on DP table size. Monitor memory growth rate during DP computation. Use streaming approaches for very large n when possible.
Interview Questions
If the problem can be phrased as "what's the answer for prefix [0..i]?" and the answer for position i only depends on some subset of positions {0..i-1}, 1D DP likely applies. The key is whether you can define dp[i] meaningfully. If you need to remember information about earlier positions that aren't captured by a single index, you might need 2D DP or another approach.
When the recurrence for dp[i] only depends on a constant number of previous values. For Fibonacci-style dp[i] = dp[i-1] + dp[i-2], you only need the previous two values. However, for recurrences like dp[i] = sum(dp[j]) for all j < i, you need the full history. The rule: if dp[i] depends on dp[i-k] for fixed maximum k, you can use O(k) space. If it depends on all previous values, you need O(n) space.
LIS (Longest Increasing Subsequence) is 1D: you're finding a subsequence within a single sequence where elements are increasing. The sequence must maintain relative order but elements don't need to be adjacent. LCS (Longest Common Subsequence) is 2D: finding a subsequence common to two sequences. LCS requires comparing positions in both strings, hence 2D DP. LIS is O(n²) or O(n log n); LCS is O(n×m).
The circular constraint means you can't rob both the first and last house since they're adjacent. The trick: run the linear solution twice—once on houses [0 to n-2] and once on [1 to n-1]—then take the maximum. This handles the two cases: either you exclude the last house, or you exclude the first house. You can't include both by definition of the circular constraint.
Optimal substructure means the optimal solution to a problem can be constructed from the optimal solutions to its subproblems. In 1D DP, this means dp[i] can be computed from optimal values of dp[j] for j < i. Without optimal substructure, DP cannot be applied — you'd need to explore all possibilities. Most linear optimization problems like shortest path, longest subsequence, and resource allocation exhibit this property.
Kadane's algorithm is a classic 1D DP where dp[i] = max(nums[i], nums[i] + dp[i-1]). dp[i] represents the maximum subarray sum ending at position i. At each step, you decide: start a new subarray at i (nums[i]) or extend the previous subarray (nums[i] + dp[i-1]). The global maximum is tracked separately. The space optimization is O(1) since only dp[i-1] is needed.
Decode Ways (LeetCode 91) asks how many ways to decode a digit string where 'A'=1 through 'Z'=26. The recurrence: dp[i] = dp[i-1] (if s[i] != '0') + dp[i-2] (if s[i-1:i+1] is between "10" and "26"). dp[i] represents ways to decode prefix of length i. Base cases: dp[0] = 1 (empty string), dp[1] = 1 if s[0] != '0' else 0. Space can be optimized to O(1) using two variables.
Top-down memoization has three advantages: (1) It only computes subproblems that are actually needed, which can be faster when the state space is sparse. (2) Recursive definitions often mirror the natural recurrence more directly, making code easier to write. (3) It avoids figuring out the correct computation order. However, bottom-up is usually preferred in production because it avoids recursion depth limits, has no function call overhead, and gives explicit control over memory layout for space optimization.
In Coin Change 2, iterating coins in the outer loop ensures each combination is counted once — the order of coins doesn't matter since we consider each coin denomination as we go. If amount were in the outer loop, we'd count permutations (different orderings of the same coins). For the original coin change (min coins), order doesn't affect the minimum count, so the loop order is interchangeable. This distinction between combinations vs permutations in DP loop ordering is a common interview trap.
Jump Game (LeetCode 55) asks whether you can reach the last index given an array where nums[i] represents the maximum jump length from position i. The DP approach: dp[i] = True if there exists j < i where dp[j] is True and j + nums[j] >= i. This is O(n²). However, greedy works in O(n): keep track of the farthest reachable position as you iterate. If at any point the current index exceeds the farthest reachable, return False. The greedy approach exploits the fact that once you know you can reach a position, you only need the maximum jump from all reachable positions so far.
Kadane's algorithm is essentially 1D DP with optimization. The DP formulation: dp[i] = max(nums[i], dp[i-1] + nums[i]) where dp[i] is the maximum subarray sum ending at index i. The global maximum is the answer. Space optimizes to O(1) because dp[i] only depends on dp[i-1]. The key insight is that you either extend the previous subarray or start fresh at the current element — this local decision yields the global optimum.
Coin Change 2 (LeetCode 518) counts the number of combinations that sum to amount using unlimited coins of different denominations. The recurrence: dp[i] += dp[i - coin] for each coin. The outer loop iterates over coins, inner loop over amounts. This order matters because it ensures each combination is counted once — we process all ways to reach each amount using the current coin before moving to the next coin. Reversing the loops counts permutations (different orderings). The result is dp[amount] after processing all coins.
Unique Paths (62) counts ways to reach bottom-right from top-left moving only right/down. The recurrence: dp[i][j] = dp[i-1][j] + dp[i][j-1]. Space can be optimized to O(n) using a 1D array where dp[j] represents paths to current row. Minimum Path Sum (64) adds costs — dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1]). Both are 2D problems that can use 1D space optimization because each row only depends on the current row and the previous row. The key difference: addition vs. min operation for combining subproblems.
Longest Palindromic Subsequence (LPS) is typically solved with 2D DP where dp[i][j] = LPS length in substring s[i:j+1]. The recurrence: if s[i] == s[j], dp[i][j] = dp[i+1][j-1] + 2; else dp[i][j] = max(dp[i+1][j], dp[i][j-1]). However, you can use 1D DP by processing the string in reverse and treating it like LIS on the reversed string. The 2D approach is more intuitive for palindrome problems because you need to track both ends of the substring. LPS relates to Longest Common Subsequence where you compare the string with its reverse.
Decode Ways (91) counts ways to decode a message where 'A'=1 through 'Z'=26. The tricky parts: (1) Strings starting with '0' are invalid — '0' can only be decoded as part of '10' or '20'. (2) You must check both single-digit (s[i] != '0') and double-digit (s[i-1:i+1] between "10" and "26") valid decodings. (3) Invalid inputs like "30" or "06" should return 0. The recurrence: dp[i] = (dp[i-1] if valid single) + (dp[i-2] if valid double). Base cases: dp[0] = 1 if s[0] != '0', else 0. Space can be optimized to O(1) with two variables tracking dp[i-1] and dp[i-2].
The classic "Best Time to Buy and Sell Stock" (121) asks for maximum profit with one transaction. The 1D DP approach: track the minimum price seen so far and the maximum profit. At each day, profit = price - min_price_sofar, update max_profit if this is better. This is technically O(n) time O(1) space — not classic DP but shares the same incremental optimization principle. The recurrence is implicit: max_profit[i] = max(max_profit[i-1], prices[i] - min_price[i-1]). For the k-transaction version, you need 2D DP where dp[i][j] is max profit on day i with j transactions.
Word Break (139) checks if a string can be segmented into dictionary words. The naive DP: dp[i] = OR(dp[j] AND s[j:i] in dict) for all j < i. This is O(n²) because for each position i, you check all previous positions j. Optimization approaches: (1) Sort dictionary by length and only check j positions where i - j <= max_word_length. (2) Use a trie to quickly test if s[j:i] is in the dictionary. (3) For very large inputs, you can combine BFS/DFS with memoization. The n² is inherent in the worst case since you might need to check all substring boundaries — but practical optimizations can significantly reduce constant factors.
House Robber II (213) adds a circular constraint: the first and last houses are adjacent, so you cannot rob both. The solution: run the linear house robber twice on two subarrays — nums[0:n-1] and nums[1:n] — and take the maximum. This works because any valid solution must exclude either the first house or the last house (or both). The DP remains the same: dp[i] = max(dp[i-1], dp[i-2] + nums[i]). The circular constraint just means you lose the ability to use the "full array" solution. Edge case: if n=1, return nums[0]. If n=2, return max(nums[0], nums[1]).
The basic climbing stairs allows 1 or 2 steps. The generalization: given a list of allowed step sizes (e.g., [1, 2, 3, 5]), count ways to reach nth stair. The recurrence: dp[i] = sum(dp[i - step] for step in steps if i >= step). Base case: dp[0] = 1 (one way to stay at start). This is essentially a bounded/unbounded knapsack problem where order matters. For example, with steps [1, 2], dp[3] = dp[2] + dp[1] = 2 + 1 = 3 ways. Space can be optimized to O(1) by keeping only the last k states where k is the maximum step size.
The systematic approach: (1) Identify what the "index" represents — usually position i in an array or prefix of length i. (2) Define dp[i] precisely — what does it represent? (3) Find the recurrence by asking: "how does the answer at i relate to answers at smaller indices?" (4) Identify base cases — what are dp[0], dp[1]? (5) Determine space optimization potential — does dp[i] only depend on last k states? (6) Consider top-down vs bottom-up trade-offs. Example: for "maximum sum of non-adjacent elements", define dp[i] as max sum considering elements 0..i where i is included or not, leading to dp[i] = max(dp[i-1], dp[i-2] + nums[i]). Practice with varied problems builds intuition for recognizing patterns.
Further Reading
Books and Courses
- “Introduction to Algorithms” (CLRS) — Chapters 15 (Dynamic Programming) and 25 (All-Pairs Shortest Paths) provide rigorous theoretical foundations.
- “Algorithm Design Manual” by Skiena — Chapter 8 (Dynamic Programming) has an excellent problem-driven approach with a catalog of DP problems.
- “Cracking the Coding Interview” — DP problems in the chapter on recursion and dynamic programming, with step-by-step walkthroughs.
Online Resources
- LeetCode 1D DP Problem Set — Curated list: Climbing Stairs (70), House Robber (198), Coin Change (322), Decode Ways (91), Maximum Subarray (53), Word Break (139), Longest Increasing Subsequence (300).
- GeeksforGeeks DP Tutorial — Comprehensive guide with categorized problems and complexity analysis.
- MIT OpenCourseWare 6.006 — Lectures on DP including Fibonacci, shortest paths, and edit distance.
Advanced Topics
- DP with Bitmasking — When the state space includes subsets, 1D DP extends to DP over subsets (e.g., traveling salesman problem).
- Digit DP — A specialized 1D DP technique for counting numbers with certain digit properties in a range.
- DP on Trees — When the “index” becomes a tree node instead of a linear position, recurrences follow edges rather than indices.
- Convex Hull Trick — Optimizing DP recurrences with linear functions for O(n log n) or O(n) time.
- Divide and Conquer DP Optimization — When dp[i] = min(dp[j] + cost(j+1, i)) and cost satisfies quadrangle inequality (Knuth optimization).
Conclusion
Once you’re comfortable with 1D DP, 2D DP is the next step. 1D trains you to think about one prefix. 2D asks you to track two at once — like LCS comparing two strings, or matrix chain multiplication where your state spans a range. Same core idea, bigger table.
For the next step, see /blog/technical/2d-dp-problems/.
Category
Related Posts
2D Dynamic Programming: Matrix Chain and Beyond
Master 2D DP problems with two state variables for string manipulation, matrix chain multiplication, and optimal game strategies.
DP States and Transitions: Building Optimal Solutions
Learn how to identify optimal substructure, define DP state variables, and formulate recurrence relations correctly.
Dynamic Programming: From Memoization to Optimal Solutions
Master dynamic programming fundamentals including memoization, tabulation, and how to identify DP subproblems.