# 完全背包
# w[i] 第i种物品的体积
# v[i] 第i种物品的价值
# 每种物品无限次重复选
# 返回：在所选物品体积不超过capacity的情况下，所能得到的最大价值和
def unbounded_knapsack(capacity: int, w: List[int], v: List[int]):
    n = len(w)
    @cache
    def dfs(i, c):
        if i < 0:
            return 0
        # 只能不选这一种
        if c < w[i]:
            return dfs(i-1,c)
        return max(dfs(i, c-w[i])+v[i], dfs(i-1, c))
    return dfs(n-1, capacity)

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        n = len(coins)
        @cache
        def dfs(i, c):
            if i < 0:
                return 0 if c == 0 else inf
            # 只能不选这一种
            if c < coins[i]:
                return dfs(i-1,c)
            return min(dfs(i, c-coins[i]) + 1, dfs(i-1, c))
        ans = dfs(n-1, amount)
        return ans if ans != inf else -1

# 完全背包
# w[i] 第i种物品的体积
# v[i] 第i种物品的价值
# 每种物品无限次重复选
# 返回：在所选物品体积不超过capacity的情况下，所能得到的最大价值和
def unbounded_knapsack(capacity: int, w: List[int], v: List[int]):
    n = len(w)
    @cache
    def dfs(i, c):
        if i < 0:
            return 0
        # 只能不选这一种
        if c < w[i]:
            return dfs(i-1,c)
        return max(dfs(i, c-w[i])+v[i], dfs(i-1, c))
    return dfs(n-1, capacity)

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        # n = len(coins)
        # @cache
        # def dfs(i, c):
        #     if i < 0:
        #         return 0 if c == 0 else inf
        #     # 只能不选这一种
        #     if c < coins[i]:
        #         return dfs(i-1,c)
        #     return min(dfs(i, c-coins[i]) + 1, dfs(i-1, c))
        # ans = dfs(n-1, amount)
        # return ans if ans != inf else -1
        n = len(coins)
        f = [[inf] * (amount+1) for _ in range(n+1)] # 注意顺序
        f[0][0] = 0
        # f[i][c] = min(f[i][c-coins[i]] + 1, f[i-1][c])
        # f[i+1][c] = min(f[i+1][c-coins[i]] + 1, f[i][c])
        for i, x in enumerate(coins):
            for c in range(amount+1): # 注意+1
                if c < x:
                    f[i+1][c] = f[i][c]
                else:
                    f[i+1][c] = min(f[i+1][c-x]+1, f[i][c])
        return f[n][amount] if f[n][amount] < inf else -1

# 完全背包
# w[i] 第i种物品的体积
# v[i] 第i种物品的价值
# 每种物品无限次重复选
# 返回：在所选物品体积不超过capacity的情况下，所能得到的最大价值和
def unbounded_knapsack(capacity: int, w: List[int], v: List[int]):
    n = len(w)
    @cache
    def dfs(i, c):
        if i < 0:
            return 0
        # 只能不选这一种
        if c < w[i]:
            return dfs(i-1,c)
        return max(dfs(i, c-w[i])+v[i], dfs(i-1, c))
    return dfs(n-1, capacity)

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        # n = len(coins)
        # @cache
        # def dfs(i, c):
        #     if i < 0:
        #         return 0 if c == 0 else inf
        #     # 只能不选这一种
        #     if c < coins[i]:
        #         return dfs(i-1,c)
        #     return min(dfs(i, c-coins[i]) + 1, dfs(i-1, c))
        # ans = dfs(n-1, amount)
        # return ans if ans != inf else -1
        n = len(coins)
        f = [[inf] * (amount+1) for _ in range(2)] # 注意顺序
        f[0][0] = 0
        # f[i][c] = min(f[i][c-coins[i]] + 1, f[i-1][c])
        # f[i+1][c] = min(f[i+1][c-coins[i]] + 1, f[i][c])
        for i, x in enumerate(coins):
            for c in range(amount+1): # 注意+1
                if c < x:
                    f[(i+1)%2][c] = f[i%2][c]
                else:
                    f[(i+1)%2][c] = min(f[(i+1)%2][c-x]+1, f[i%2][c])
        return f[n%2][amount] if f[n%2][amount] < inf else -1