Coin Change

01 · Question

You are given an integer array coins and an integer amount. Return the fewest number of coins needed to make up that amount. If it is not possible, return -1.

02 · Analysis

Coin denominations are positive and may be reused; amount is nonnegative. dp[a] is the fewest coins for exact amount a. Try each coin no larger than a and use 1+dp[a-coin]; initialize dp[0]=0 and other states as impossible. Processing amounts upward makes every smaller amount ready. For m denominations and amount A, time O(Am), space O(A). Amount 0 needs 0 coins; an unreachable amount returns -1.

03 · Solution

Reference solution

1def coinChange(coins: List[int], amount: int) -> int:
2    dp = [amount + 1] * (amount + 1)
3    dp[0] = 0
4
5    for a in range(1, amount + 1):
6        for c in coins:
7            if a - c >= 0:
8                dp[a] = min(dp[a], 1 + dp[a - c])
9
10    return -1 if dp[amount] == amount + 1 else dp[amount]

House Robber

Longest Increasing Subsequence