1D Dynamic Programming Interview Patterns
1D DP problems have a state space that reduces to a single index or value. The recurrence depends only on a constant number of previous states, enabling O(N) time and O(1) space solutions after recognizing the pattern.
Pattern 1: Linear Sequence (House Robber)
def rob(nums):
prev2, prev1 = 0, 0
for n in nums:
prev2, prev1 = prev1, max(prev1, prev2 + n)
return prev1
# dp[i] = max(dp[i-1], dp[i-2] + nums[i])
# "take or skip" recurrence
Applications: House Robber I/II, Maximum Alternating Subsequence, any “pick non-adjacent elements” problem. Space optimization: only need prev two values → O(1) space.
Pattern 2: Climbing Stairs / Fibonacci-style
def climb_stairs(n):
a, b = 1, 1
for _ in range(2, n+1):
a, b = b, a + b
return b
# dp[i] = dp[i-1] + dp[i-2]
Applications: Climbing Stairs, Decode Ways (count decodings of digit string), Min Cost Climbing Stairs. Decode Ways adds validity check: single digit (not 0) or two digits (10–26) must be valid.
Pattern 3: Unbounded Knapsack (Coin Change)
def coin_change(coins, amount):
dp = [float('inf')] * (amount + 1)
dp[0] = 0
for a in range(1, amount + 1):
for c in coins:
if c <= a:
dp[a] = min(dp[a], dp[a - c] + 1)
return dp[amount] if dp[amount] != float('inf') else -1
Unbounded: each item (coin) can be used multiple times. Iterate amounts outer, coins inner. 0/1 Knapsack (each item once): iterate items outer, amounts inner (backward to prevent reuse).
Pattern 4: Longest Increasing Subsequence (LIS)
# O(N^2) DP
def lis_n2(nums):
dp = [1] * len(nums)
for i in range(1, len(nums)):
for j in range(i):
if nums[j] < nums[i]:
dp[i] = max(dp[i], dp[j] + 1)
return max(dp)
# O(N log N) patience sorting
def lis_nlogn(nums):
tails = []
for n in nums:
lo, hi = 0, len(tails)
while lo < hi:
mid = (lo+hi)//2
if tails[mid] < n: lo = mid+1
else: hi = mid
if lo == len(tails): tails.append(n)
else: tails[lo] = n
return len(tails)
The patience sorting approach maintains a list of “tail” values of increasing subsequences. Binary search finds where to place each number. Length of tails = LIS length.
Pattern 5: Palindromic Subsequence
def longest_palindromic_subseq(s):
n = len(s)
dp = [[0]*n for _ in range(n)]
for i in range(n): dp[i][i] = 1
for length in range(2, n+1):
for i in range(n-length+1):
j = i + length - 1
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])
return dp[0][n-1]
Pattern 6: Word Break
def word_break(s, word_dict):
word_set = set(word_dict)
dp = [False] * (len(s)+1)
dp[0] = True
for i in range(1, len(s)+1):
for j in range(i):
if dp[j] and s[j:i] in word_set:
dp[i] = True
break
return dp[len(s)]
Recognizing 1D DP Problems
- “Maximum/minimum over a sequence” + optimal substructure → DP
- Counting distinct ways → DP (sum over valid previous states)
- Decision at each element: take or skip → House Robber pattern
- String segmentation or matching → Word Break / Decode Ways
{
“@context”: “https://schema.org”,
“@type”: “FAQPage”,
“mainEntity”: [
{
“@type”: “Question”,
“name”: “What is the space-optimized approach for House Robber and why does it work?”,
“acceptedAnswer”: { “@type”: “Answer”, “text”: “House Robber (LeetCode 198): you cannot rob two adjacent houses. DP recurrence: dp[i] = max(dp[i-1], dp[i-2] + nums[i]). At each step, you either skip the current house (take dp[i-1]) or rob it (take dp[i-2] + value). Since dp[i] only depends on the two previous states, you can eliminate the array: maintain prev2 (dp[i-2]) and prev1 (dp[i-1]), update in a single pass. Space O(1). The same optimization applies to Fibonacci, Climb Stairs, and any 1D DP where the recurrence only looks back a fixed number of steps. The key insight: if dp[i] depends only on dp[i-1] and dp[i-2], rolling variables replace the full array.” }
},
{
“@type”: “Question”,
“name”: “How does patience sorting achieve O(N log N) Longest Increasing Subsequence?”,
“acceptedAnswer”: { “@type”: “Answer”, “text”: “The O(N^2) LIS DP is too slow for N=10^5. Patience sorting uses a tails array where tails[i] is the smallest tail element of all increasing subsequences of length i+1. For each number, binary search in tails for the leftmost position where tails[pos] >= num and replace it (or append if larger than all). The length of tails at the end equals the LIS length. Why it works: tails is always sorted (maintaining the invariant), so binary search is valid. Each element is processed in O(log N), total O(N log N). In Python: use bisect_left(tails, num) for strictly increasing (replace tails[pos] = num if found, else append). For non-strictly increasing: use bisect_right. The tails array does NOT directly encode the actual subsequence — reconstruct using a parent pointer array if the actual LIS elements are needed.” }
},
{
“@type”: “Question”,
“name”: “How do you recognize Coin Change as unbounded knapsack and solve it?”,
“acceptedAnswer”: { “@type”: “Answer”, “text”: “Coin Change (minimum coins to make amount) is unbounded knapsack: each coin can be used unlimited times. dp[i] = minimum coins to make amount i. Initialize dp[0]=0, dp[1..amount]=infinity. For each amount i from 1 to amount: for each coin c <= i: dp[i] = min(dp[i], dp[i-c] + 1). Key property: iterating amounts in ascending order and allowing re-use of coins in the inner loop gives unbounded knapsack. For 0/1 knapsack (each item once), iterate items in outer loop and amounts in descending order. Common mistake: initializing dp with 0 instead of infinity — then 0 propagates and every amount appears reachable. Check: if dp[amount] == infinity, return -1. For Coin Change 2 (count ways): dp[i] += dp[i-c] — the transition adds combinations, not minimums.” }
}
]
}