LC322—零钱兑换

Java架构师必看

修改于 2023-09-25 07:05:37

48800

代码可运行

文章被收录于专栏：Java架构师必看Java架构师必看

运行总次数：0

代码可运行

322. 零钱兑换

难度中等1087

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

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

示例 1：

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

示例 2：

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

动态规划:详细题解

class Solution {
   
  
    public int coinChange(int[] coins, int amount) {
   
       //自底向上的动态规划
        if (coins.length == 0) {
   
            return -1;
        }

        // memo[n]的值： 表示的凑成总金额为n所需的最少的硬币个数
        int[] memo = new int[amount +1];
        //给memo赋值,最多的硬币数就是全部使用面值为1的硬币进行换
        //amont+1 是不可能达到的换取数量,,于是使用其进行填充
         Arrays.fill(memo, amount + 1);
        memo[0] = 0;
        for (int i = 1; i <= amount; i++) {
   
            for (int j = 0; j < coins.length; j++) {
   
                if (i - coins[j] >= 0) {
   
                    // memo[i]有两种实现的方式，
                    /*一种是包含当前的coins[i],那么剩余钱就是 i-coins[i] 这种操作要兑换的硬币数是 memo[i-coins[j]] + 1 */
                    //另外一种就是另一种就是不包含，要兑换的硬币数是memo[i]
                    memo[i] = Math.min(memo[i], memo[i - coins[j]] + 1);
                }
            }
        }
        return memo[amount] == (amount + 1) ? -1 : memo[amount];
    }
}