Intermediate

1D DP Problems

Six classic problems where the DP state is a single variable. Each problem follows the progression: brute force recursion, memoization, tabulation, and space optimization. These problems appear in over 60% of coding interviews that include DP.

Problem 1: Climbing Stairs

Problem: You are climbing a staircase with n steps. Each time you can climb 1 or 2 steps. How many distinct ways can you reach the top?

State: dp[i] = number of ways to reach step i.

Recurrence: dp[i] = dp[i-1] + dp[i-2] (you arrive from one step below or two steps below).

# Brute force: O(2^n) time
def climb_brute(n):
    if n <= 1:
        return 1
    return climb_brute(n - 1) + climb_brute(n - 2)

# Memoization: O(n) time, O(n) space
from functools import lru_cache

@lru_cache(maxsize=None)
def climb_memo(n):
    if n <= 1:
        return 1
    return climb_memo(n - 1) + climb_memo(n - 2)

# Tabulation: O(n) time, O(1) space
def climb_tab(n):
    if n <= 1:
        return 1
    prev2, prev1 = 1, 1
    for i in range(2, n + 1):
        curr = prev1 + prev2
        prev2 = prev1
        prev1 = curr
    return prev1

# Test: climb_tab(5) = 8, climb_tab(10) = 89

Problem 2: House Robber

Problem: You are a robber planning to rob houses along a street. Each house has a certain amount of money. Adjacent houses have connected security systems — if two adjacent houses are robbed on the same night, the police are alerted. Find the maximum amount you can rob without alerting the police.

State: dp[i] = maximum money from robbing houses 0..i.

Recurrence: dp[i] = max(dp[i-1], dp[i-2] + nums[i]). Either skip house i (take dp[i-1]) or rob house i (take dp[i-2] + nums[i]).

# Brute force: O(2^n) time - try every subset of non-adjacent houses
def rob_brute(nums, i=None):
    if i is None:
        i = len(nums) - 1
    if i < 0:
        return 0
    # Choice: skip house i, or rob house i and skip i-1
    return max(rob_brute(nums, i - 1),
               rob_brute(nums, i - 2) + nums[i])

# Memoization: O(n) time, O(n) space
def rob_memo(nums):
    memo = {}
    def dp(i):
        if i < 0:
            return 0
        if i in memo:
            return memo[i]
        memo[i] = max(dp(i - 1), dp(i - 2) + nums[i])
        return memo[i]
    return dp(len(nums) - 1)

# Tabulation: O(n) time, O(1) space
def rob_tab(nums):
    if not nums:
        return 0
    if len(nums) == 1:
        return nums[0]
    prev2, prev1 = 0, nums[0]
    for i in range(1, len(nums)):
        curr = max(prev1, prev2 + nums[i])
        prev2 = prev1
        prev1 = curr
    return prev1

# Test: rob_tab([2,7,9,3,1]) = 12 (rob houses 0,2,4: 2+9+1=12)

💡

Pattern insight: House robber is the "include/exclude" pattern. At each step you decide to include the current element (and skip the previous) or exclude it. This pattern appears in dozens of DP problems.

Problem 3: Coin Change

Problem: Given coins of different denominations and a total amount, find the minimum number of coins needed to make that amount. Return -1 if it cannot be made.

State: dp[amount] = minimum coins to make this amount.

Recurrence: dp[amount] = min(dp[amount - coin] + 1) for each coin.

# Brute force: O(S^n) time where S = amount, n = number of coins
def coin_brute(coins, amount):
    if amount == 0:
        return 0
    if amount < 0:
        return float('inf')
    result = float('inf')
    for coin in coins:
        sub = coin_brute(coins, amount - coin)
        result = min(result, sub + 1)
    return result if result != float('inf') else -1

# Memoization: O(amount * len(coins)) time
def coin_memo(coins, amount):
    memo = {}
    def dp(rem):
        if rem == 0:
            return 0
        if rem < 0:
            return float('inf')
        if rem in memo:
            return memo[rem]
        memo[rem] = float('inf')
        for coin in coins:
            memo[rem] = min(memo[rem], dp(rem - coin) + 1)
        return memo[rem]
    result = dp(amount)
    return result if result != float('inf') else -1

# Tabulation: O(amount * len(coins)) time, O(amount) space
def coin_tab(coins, amount):
    dp = [float('inf')] * (amount + 1)
    dp[0] = 0
    for i in range(1, amount + 1):
        for coin in coins:
            if coin <= i and dp[i - coin] + 1 < dp[i]:
                dp[i] = dp[i - coin] + 1
    return dp[amount] if dp[amount] != float('inf') else -1

# Test: coin_tab([1,5,10,25], 30) = 2 (one 5 + one 25)

Problem 4: Longest Increasing Subsequence (LIS)

Problem: Given an integer array, find the length of the longest strictly increasing subsequence.

State: dp[i] = length of the longest increasing subsequence ending at index i.

Recurrence: dp[i] = max(dp[j] + 1) for all j < i where nums[j] < nums[i].

# Brute force: O(2^n) - try all subsequences
def lis_brute(nums):
    def helper(prev_idx, curr_idx):
        if curr_idx == len(nums):
            return 0
        # Option 1: skip current element
        taken = 0
        not_taken = helper(prev_idx, curr_idx + 1)
        # Option 2: take current if it's greater than previous
        if prev_idx == -1 or nums[curr_idx] > nums[prev_idx]:
            taken = 1 + helper(curr_idx, curr_idx + 1)
        return max(taken, not_taken)
    return helper(-1, 0)

# Tabulation: O(n^2) time, O(n) space
def lis_tab(nums):
    if not nums:
        return 0
    n = len(nums)
    dp = [1] * n  # Every element is a subsequence of length 1
    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)

# Optimal: O(n log n) using patience sorting / binary search
import bisect

def lis_optimal(nums):
    tails = []  # tails[i] = smallest tail of all increasing subsequences of length i+1
    for num in nums:
        pos = bisect.bisect_left(tails, num)
        if pos == len(tails):
            tails.append(num)
        else:
            tails[pos] = num
    return len(tails)

# Test: lis_optimal([10,9,2,5,3,7,101,18]) = 4 ([2,3,7,101])

📝

Why O(n log n)? The tails array is always sorted. For each new element, we binary search for its position. If it extends the longest subsequence, we append it. Otherwise, we replace the first element in tails that is >= to it. This maintains the invariant that tails[i] is the smallest possible tail for a subsequence of length i+1.

Problem 5: Maximum Subarray (Kadane's Algorithm)

Problem: Given an integer array, find the contiguous subarray with the largest sum.

State: dp[i] = maximum subarray sum ending at index i.

Recurrence: dp[i] = max(nums[i], dp[i-1] + nums[i]). Either start a new subarray at i or extend the previous one.

# Brute force: O(n^2) - try all subarrays
def max_sub_brute(nums):
    best = float('-inf')
    for i in range(len(nums)):
        curr_sum = 0
        for j in range(i, len(nums)):
            curr_sum += nums[j]
            best = max(best, curr_sum)
    return best

# Tabulation (Kadane's): O(n) time, O(1) space
def max_sub_kadane(nums):
    max_ending_here = nums[0]
    max_so_far = nums[0]
    for i in range(1, len(nums)):
        max_ending_here = max(nums[i], max_ending_here + nums[i])
        max_so_far = max(max_so_far, max_ending_here)
    return max_so_far

# Test: max_sub_kadane([-2,1,-3,4,-1,2,1,-5,4]) = 6 ([4,-1,2,1])

Problem 6: Decode Ways

Problem: A message containing letters A-Z is encoded as numbers (A=1, B=2, ..., Z=26). Given a string of digits, determine how many ways it can be decoded.

State: dp[i] = number of ways to decode the first i characters.

Recurrence: If s[i-1] is valid (1-9), dp[i] += dp[i-1]. If s[i-2:i] is valid (10-26), dp[i] += dp[i-2].

# Brute force: O(2^n) time
def decode_brute(s, idx=0):
    if idx == len(s):
        return 1
    if s[idx] == '0':
        return 0
    # Take one digit
    ways = decode_brute(s, idx + 1)
    # Take two digits if valid (10-26)
    if idx + 1 < len(s) and int(s[idx:idx+2]) <= 26:
        ways += decode_brute(s, idx + 2)
    return ways

# Memoization: O(n) time, O(n) space
def decode_memo(s):
    memo = {}
    def dp(idx):
        if idx == len(s):
            return 1
        if s[idx] == '0':
            return 0
        if idx in memo:
            return memo[idx]
        ways = dp(idx + 1)
        if idx + 1 < len(s) and int(s[idx:idx+2]) <= 26:
            ways += dp(idx + 2)
        memo[idx] = ways
        return ways
    return dp(0)

# Tabulation: O(n) time, O(1) space
def decode_tab(s):
    if not s or s[0] == '0':
        return 0
    n = len(s)
    prev2 = 1  # dp[i-2]: empty string
    prev1 = 1  # dp[i-1]: first character
    for i in range(2, n + 1):
        curr = 0
        # Single digit: s[i-1]
        if s[i-1] != '0':
            curr += prev1
        # Two digits: s[i-2:i]
        two_digit = int(s[i-2:i])
        if 10 <= two_digit <= 26:
            curr += prev2
        prev2 = prev1
        prev1 = curr
    return prev1

# Test: decode_tab("226") = 3 ("BZ", "VF", "BBF")
# Test: decode_tab("06") = 0 (leading zero is invalid)

Complexity Summary

Problem	Brute Force	DP Time	DP Space	Optimized Space
Climbing Stairs	O(2^n)	O(n)	O(n)	O(1)
House Robber	O(2^n)	O(n)	O(n)	O(1)
Coin Change	O(S^n)	O(amount × coins)	O(amount)	O(amount)
LIS	O(2^n)	O(n^2)	O(n)	O(n log n)
Maximum Subarray	O(n^2)	O(n)	O(n)	O(1)
Decode Ways	O(2^n)	O(n)	O(n)	O(1)

Key Takeaways

All six problems use a single variable as the DP state, making them the simplest DP category.
The include/exclude pattern (house robber, decode ways) appears in many DP variants: at each step, decide whether to include the current element.
Space optimization from O(n) to O(1) is possible when dp[i] only depends on dp[i-1] and dp[i-2].
LIS is special: the O(n^2) DP solution can be improved to O(n log n) using binary search on a patience-sorting array.
Kadane's algorithm is DP in disguise — it maintains the maximum subarray sum ending at each position.

← Previous DP Fundamentals Next → 2D DP Problems