1D Dynamic Programming Problems: House Robber, Coin Change and LIS

In one-dimensional DP, the state is a single number, usually a position in a list or an amount: dp[i]. These problems use the five-step method: define the state, write the recurrence, set base cases, pick the order, read the answer.

House robber#

Houses in a row hold some money. You cannot rob two neighbouring houses. What is the most you can take?

• State: dp[i] = the most money from the first i + 1 houses.
• Recurrence: at house i, either skip it (dp[i-1]) or rob it plus the best up to house i − 2 (dp[i-2] + money[i]).

def rob(money):
    if not money:
        return 0
    prev2, prev1 = 0, 0               # best up to i-2 and i-1
    for m in money:
        prev2, prev1 = prev1, max(prev1, prev2 + m)
    return prev1

print(rob([2, 7, 9, 3, 1]))
print(rob([5, 1, 1, 5]))

12
10

For [2, 7, 9, 3, 1] the best is 2 + 9 + 1 = 12. For [5, 1, 1, 5] it is both 5s: 10. A greedy "take the biggest house" idea would not find these.

Coin change: fewest coins#

Given coin values and an amount, find the fewest coins that make the amount, or -1.

• State: dp[a] = fewest coins that make amount a.
• Recurrence: dp[a] = 1 + min(dp[a - c]) over every coin c ≤ a.
• Base: dp[0] = 0.

def min_coins(coins, amount):
    INF = float("inf")
    dp = [0] + [INF] * amount
    for a in range(1, amount + 1):
        for c in coins:
            if c <= a and dp[a - c] + 1 < dp[a]:
                dp[a] = dp[a - c] + 1
    return dp[amount] if dp[amount] != INF else -1

print(min_coins([1, 3, 4], 6))
print(min_coins([2], 3))
print(min_coins([1, 2, 5], 11))

2
-1
3

O(amount × number of coins) time. This is the problem where greedy fails and DP succeeds.

Counting ways to make change#

How many different combinations of coins make the amount? Looping over coins on the outside counts each combination once, regardless of order:

def count_ways(coins, amount):
    dp = [1] + [0] * amount            # one way to make 0: use nothing
    for c in coins:
        for a in range(c, amount + 1):
            dp[a] += dp[a - c]
    return dp[amount]

print(count_ways([1, 2, 5], 5))
print(count_ways([2, 5, 3, 6], 10))

4
5

The 4 ways to make 5 are 5, 2+2+1, 2+1+1+1 and 1+1+1+1+1. Swapping the two loops would count 1+2 and 2+1 separately (ordered sequences), which is a different question.

Decode ways#

Letters are encoded as numbers: A = 1, B = 2, …, Z = 26. How many ways can a string of digits be decoded?

• State: dp[i] = ways to decode the first i characters.
• Recurrence: the last character alone (if it is not "0") gives dp[i-1] ways; the last two characters (if they form 10 to 26) add dp[i-2].

def decode_ways(s):
    dp = [0] * (len(s) + 1)
    dp[0] = 1
    for i in range(1, len(s) + 1):
        if s[i - 1] != "0":
            dp[i] += dp[i - 1]
        if i >= 2 and 10 <= int(s[i - 2:i]) <= 26:
            dp[i] += dp[i - 2]
    return dp[len(s)]

print(decode_ways("12"))
print(decode_ways("226"))
print(decode_ways("06"))

2
3
0

"226" decodes as 2-2-6 (BBF), 22-6 (VF) or 2-26 (BZ). "06" has no decoding, because no letter is "06".

Maximum subarray (Kadane's algorithm)#

Find the largest sum of a contiguous part of a list (numbers may be negative).

• State: best_ending_here = the largest sum of a subarray that ends at the current position.
• Recurrence: either extend the previous subarray or start fresh here: max(x, best_ending_here + x).

def max_subarray(nums):
    best_ending_here = best = nums[0]
    for x in nums[1:]:
        best_ending_here = max(x, best_ending_here + x)
        best = max(best, best_ending_here)
    return best

print(max_subarray([-2, 1, -3, 4, -1, 2, 1, -5, 4]))
print(max_subarray([-3, -1, -2]))

6
-1

The best part is [4, -1, 2, 1] with sum 6. O(n) time, O(1) space.

Longest increasing subsequence#

Find the length of the longest subsequence (not necessarily contiguous) whose values strictly increase.

• State: dp[i] = length of the longest increasing subsequence ending at index i.
• Recurrence: dp[i] = 1 + max(dp[j]) over all j < i with nums[j] < nums[i].

def lis(nums):
    dp = [1] * len(nums)
    for i in range(len(nums)):
        for j in range(i):
            if nums[j] < nums[i]:
                dp[i] = max(dp[i], dp[j] + 1)
    return max(dp, default=0)

print(lis([10, 9, 2, 5, 3, 7, 101, 18]))
print(lis([7, 7, 7]))

4
1

One longest subsequence is 2, 3, 7, 18. This version is O(n²). A cleverer method keeps, for each length, the smallest possible ending value, and finds where each number belongs with binary search: O(n log n).

from bisect import bisect_left

def lis_fast(nums):
    tails = []                     # tails[k] = smallest end of an increasing run of length k+1
    for x in nums:
        i = bisect_left(tails, x)
        if i == len(tails):
            tails.append(x)
        else:
            tails[i] = x
    return len(tails)

print(lis_fast([10, 9, 2, 5, 3, 7, 101, 18]))

4

Common mistakes#

Practice#

def word_break(s, words):
    dp = [True] + [False] * len(s)
    for i in range(1, len(s) + 1):
        for w in words:
            if len(w) <= i and dp[i - len(w)] and s[i - len(w):i] == w:
                dp[i] = True
                break
    return dp[len(s)]

print(word_break("leetcode", ["leet", "code"]))
print(word_break("applepenapple", ["apple", "pen"]))
print(word_break("catsandog", ["cats", "dog", "sand", "and", "cat"]))

True
True
False

Key takeaway#

Next: states with two indexes, in 2D Dynamic Programming.