零钱兑换(真实面试题)

2021-01-28

322. 零钱兑换

难度中等1096

给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。

你可以认为每种硬币的数量是无限的。

示例 1：

1
2
3

输入：coins = [1, 2, 5], amount = 11
输出：3 
解释：11 = 5 + 5 + 1

示例 2：

1 2	输入：coins = [2], amount = 3 输出：-1

示例 3：

1 2	输入：coins = [1], amount = 0 输出：0

示例 4：

1 2	输入：coins = [1], amount = 1 输出：1

示例 5：

1 2	输入：coins = [1], amount = 2 输出：2

提示：

1 <= coins.length <= 12
1 <= coins[i] <= 231 - 1
0 <= amount <= 104

动态规划

$F(i)=\min_{j=0 \ldots n-1} F(i-c j)+1$

背包容量是金额，coins是物品，选择是否放当前的硬币

遍历背包的容量：

对于每一件物品：

如果物品可以放入当前的容量中，就计算放入背包的收益和不放入背包的收益哪个大

不放物品是dp[i],放物品是dp[i-coins[j]]+1(其中i-coins[j]是剩余的背包容量)

public class Solution {
    public int coinChange(int[] coins, int amount) {
        int max = amount + 1;
        int[] dp = new int[amount + 1];
        Arrays.fill(dp, max);
        dp[0] = 0;
        for (int i = 1; i <= amount; i++) {
            for (int j = 0; j < coins.length; j++) {
                if (coins[j] <= i) {
                    dp[i] = Math.min(dp[i], dp[i - coins[j]] + 1);
                }
            }
        }
        return dp[amount] > amount ? -1 : dp[amount];
    }
}

作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/coin-change/solution/322-ling-qian-dui-huan-by-leetcode-solution/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

jsonContent: meta: false pages: false posts: title: true date: true path: true text: false raw: false content: false slug: false updated: false comments: false link: false permalink: false excerpt: false categories: false tags: true