Coin Change

LeetCode: https://leetcode.com/problems/coin-change/

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.

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

coins=[1, 3, 4]

amount=6

Step 1 / 6

Step 1:

dp[a] = min coins to make amount a. Initialize dp[0]=0, others=amount+1 (∞).

Focus: select @ [0]

amount=6