1-D DP classics

House robber: take it or skip it

Houses stand in a row with some money in each. You may not take from two neighbouring houses (the alarm links them). What is the most you can collect? Greedy ideas such as "take every other house" fail: for [2, 1, 1, 9] the best is 2 + 9 = 11.

State: dp[i] = the most money from the first i houses. For house i − 1 (the last one in that group) there are two choices. Skip it: dp[i − 1]. Take it: then its neighbour must be skipped, so nums[i − 1] + dp[i − 2]. Recurrence: dp[i] = max(dp[i − 1], dp[i − 2] + nums[i − 1]), with dp[0] = 0 and dp[1] = nums[0]. Only two values are read, so two variables are enough: O(n) time, O(1) space.

Coin change: the fewest coins

Given coin values (unlimited coins of each) and an amount, find the fewest coins that add up to the amount, or −1 if it cannot be done. Greedy ("always take the biggest coin that fits") works for Indian rupee coins, but fails for unusual sets: with coins [1, 3, 4] and amount 6, greedy takes 4 + 1 + 1 (three coins) while 3 + 3 uses two.

State: dp[a] = the fewest coins that make amount a. The last coin used was some c, so dp[a] = min over coins c ≤ a of dp[a − c] + 1. Base case: dp[0] = 0. Amounts that cannot be made stay at infinity, and you turn infinity into −1 at the end. Time O(amount × number of coins), space O(amount).

def coin_change_min(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(coin_change_min([1, 3, 4], 6))   # Output: 2
print(coin_change_min([2], 3))         # Output: -1

Coin change: counting the ways (loop order matters)

Now count how many different combinations of coins make the amount. With coins [1, 2] and amount 3 there are 2 combinations: 1+1+1 and 1+2. The order of coins does not matter, so 1+2 and 2+1 are the same combination.

State: ways[a] = the number of combinations that make a, with ways[0] = 1 (the empty combination). Put the coins in the OUTER loop and the amounts in the inner loop. Each coin is then "allowed" in a fixed order, so every combination is built in exactly one way: coins of the first kind, then of the second kind, and so on. If you swap the loops (amounts outside, coins inside), every ordering is counted separately and you get 3 for the example, because 1+2 and 2+1 both count. That other answer is right for a different question ("how many ordered sequences"), so read the question carefully.

def ways_combinations(coins, amount):
    ways = [1] + [0] * amount
    for c in coins:                      # coins outside
        for a in range(c, amount + 1):
            ways[a] += ways[a - c]
    return ways[amount]

def ways_orderings(coins, amount):
    ways = [1] + [0] * amount
    for a in range(1, amount + 1):       # amounts outside
        for c in coins:
            if c <= a:
                ways[a] += ways[a - c]
    return ways[amount]

print(ways_combinations([1, 2], 3), ways_orderings([1, 2], 3))   # Output: 2 3

Decode ways

A message of letters was turned into digits with A = 1, B = 2, … Z = 26. "226" could be "BZ" (2, 26), "VF" (22, 6) or "BBF" (2, 2, 6), so there are 3 ways to decode it. State: dp[i] = the number of ways to decode the first i characters, with dp[0] = 1. The last piece is either one digit (allowed if it is not "0") or two digits (allowed if they form 10 to 26). So dp[i] = (dp[i − 1] if s[i − 1] != "0") + (dp[i − 2] if 10 ≤ int(s[i − 2:i]) ≤ 26). Zeros are the trap: "06" has 0 ways, because "0" is not a letter and "06" is not allowed as a two-digit code.

Word break

Can the string be split into words from a dictionary? "applepenapple" with ["apple", "pen"] can; "catsandog" with ["cats", "dog", "sand", "and", "cat"] cannot. State: ok[i] = True if the first i characters can be split. ok[0] = True. ok[i] is True if some j < i has ok[j] True and s[j:i] in the word set. With n characters this checks O(n²) pairs, and each slice costs up to O(n), so O(n³) in the worst case; limiting j to the longest word length helps a lot.

def word_break(s, words):
    word_set = set(words)
    ok = [True] + [False] * len(s)
    for i in range(1, len(s) + 1):
        for j in range(i):
            if ok[j] and s[j:i] in word_set:
                ok[i] = True
                break
    return ok[len(s)]

print(word_break("applepenapple", ["apple", "pen"]))                     # Output: True
print(word_break("catsandog", ["cats", "dog", "sand", "and", "cat"]))   # Output: False

Common mistakes

• House robber: assuming the answer is "every other house". Fix: write the take/skip recurrence and test [2, 1, 1, 9].
• Coin change minimum: returning infinity, or 0, when the amount cannot be made. Fix: convert the "impossible" marker to −1 at the end, and test an impossible case.
• Coin change ways: putting the loops in the wrong order and counting orderings. Fix: coins outside for combinations; test coins [1, 2] with amount 3, which must give 2.
• Decode ways: forgetting that "0" cannot stand alone, or allowing "05" as a two-digit code. Fix: the one-digit piece needs s[i − 1] != "0"; the two-digit piece needs a value from 10 to 26.
• Checking word break with a list of words instead of a set, making each lookup O(k). Fix: build a set once.