Coin Change & Dynamic Programming — exercises

Answer: 4 ways. They are: $\{5\},\{2,2,1\},\{2,1,1,1\},\{1,1,1,1,1\}$.

To avoid double-counting orderings, fix the coin order: process coins one at a time, allowing repeats. State $\text{dp}[i]$ = number of ways to make amount $i$ using the coins considered so far.

def count_ways(coins, amount):
    dp = [0] * (amount + 1)
    dp[0] = 1                          # empty combination
    for c in coins:                    # outer loop over coins fixes their order
        for i in range(c, amount + 1):
            dp[i] += dp[i - c]
    return dp[amount]

print(count_ways([1, 2, 5], 5))        # 4

The order of the two loops matters: coins outside, amount inside counts unordered combinations. Amount outside, coins inside counts permutations (often called "compositions") — different problem, different answer.

Answer: 7 (take items 1 and 2 with weights 2+3 = 5, values 3+4 = 7).

def knapsack(W, V, C):
    n = len(W)
    dp = [[0]*(C+1) for _ in range(n+1)]
    for i in range(1, n+1):
        for c in range(C+1):
            dp[i][c] = dp[i-1][c]                                  # skip item i
            if W[i-1] <= c:
                dp[i][c] = max(dp[i][c],
                               dp[i-1][c - W[i-1]] + V[i-1])       # take item i
    return dp[n][C]

print(knapsack([2,3,4,5], [3,4,5,6], 5))    # 7

The recurrence: $\text{dp}[i][c]=\max (\text{dp}[i-1][c],\text{dp}[i-1][c-w_i]+v_i)$. The "0/1" comes from using $\text{dp}[i-1]$ (not $\text{dp}[i]$) on the include branch — once you take item $i$, you can't take it again. Total work: $O(nC)$.

Answer: 3. (kitten → sitten by substituting k→s; sitten → sittin by substituting e→i; sittin → sitting by inserting g.)

def edit_distance(a, b):
    m, n = len(a), len(b)
    dp = [[0]*(n+1) for _ in range(m+1)]
    for i in range(m+1): dp[i][0] = i        # delete all of a
    for j in range(n+1): dp[0][j] = j        # insert all of b
    for i in range(1, m+1):
        for j in range(1, n+1):
            if a[i-1] == b[j-1]:
                dp[i][j] = dp[i-1][j-1]      # characters match, no edit
            else:
                dp[i][j] = 1 + min(dp[i-1][j],     # delete a[i-1]
                                   dp[i][j-1],     # insert b[j-1]
                                   dp[i-1][j-1])   # substitute
    return dp[m][n]

print(edit_distance("kitten", "sitting"))    # 3

Same shape of recurrence as 0/1 knapsack — 2D state, three transitions per cell. The cost difference (min vs max, +1 vs +value) is what specializes the framework to the problem. $O(mn)$ time, $O(mn)$ space (reducible to $O(\min (m,n))$ with rolling rows).

Answer: 4. Examples: BCBA, BDAB, BCAB.

def lcs_length(a, b):
    m, n = len(a), len(b)
    dp = [[0]*(n+1) for _ in range(m+1)]
    for i in range(1, m+1):
        for j in range(1, n+1):
            if a[i-1] == b[j-1]:
                dp[i][j] = dp[i-1][j-1] + 1
            else:
                dp[i][j] = max(dp[i-1][j], dp[i][j-1])
    return dp[m][n]

print(lcs_length("ABCBDAB", "BDCABA"))    # 4

LCS is the workhorse of diff and version-control merge algorithms — what git is computing under the hood when it tells you which lines changed. Generalizations also underpin sequence alignment in bioinformatics (Needleman-Wunsch is essentially LCS with weighted edit costs).

(a) $f(10)=89$.

(b) $f(n)=f(n-1)+f(n-2)$ with $f(0)=f(1)=1$. This is the Fibonacci recurrence shifted by one: $f(n)=F_{n+1}$.

def stairs(n):
    if n < 2: return 1
    a, b = 1, 1
    for _ in range(n - 1):
        a, b = b, a + b
    return b

print(stairs(10))    # 89

This is the bare minimum DP problem — a teaching example for the technique itself. Generalizations multiply: arbitrary step sets (e.g., 5), forbidden steps, weighted steps. The 1-2 case happens to have a closed form via Binet's formula $F_n=({\varphi }^n-{\psi }^n)/\sqrt{5}$, but the tabulation is the more general approach for arbitrary step sets.

Yes — for example, $3+8=11$.

def subset_sum(S, target):
    dp = [False] * (target + 1)
    dp[0] = True
    for x in S:
        for t in range(target, x - 1, -1):     # walk backward to avoid reusing x
            dp[t] = dp[t] or dp[t - x]
    return dp[target]

print(subset_sum([2, 3, 7, 8, 10], 11))    # True

The reverse iteration is the "0/1 trick" for subset sum: walking from target down to x prevents reusing the same element multiple times within one outer-loop iteration. Subset sum is NP-hard in general (target can be exponentially large in the input size), but the DP gives pseudo-polynomial $O(n\cdot \text{target})$ — fine for small targets, infeasible for large ones.

Answer: 22. Optimal cutting: two pieces of length 2 + one piece of length 4, giving revenues $5+5+9=19$... wait let me re-verify. Optimal is one piece of length 2 + one piece of length 6: $5+17=22$. ✓

def rod_cutting(prices, n):
    dp = [0] * (n + 1)
    for length in range(1, n + 1):
        for first_cut in range(1, length + 1):
            dp[length] = max(dp[length],
                             prices[first_cut - 1] + dp[length - first_cut])
    return dp[n]

print(rod_cutting([1, 5, 8, 9, 10, 17, 17, 20], 8))    # 22

Notice the recurrence is exactly the unbounded knapsack: each cut length can be reused arbitrarily. Compare with 0/1 knapsack (P.2) where each item is unique. The two-loop ordering is the same as in P.1: iterating amount outer, choice inner gives unbounded; the other order gives 0/1. Choose the order based on whether items are reusable.