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 · 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