【动态规划】Leetcode 322. 零钱兑换【中等】

零钱兑换

• 给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。

计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。

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

示例 1：

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

解题思路

这个问题可以使用动态规划来解决

• 1、我们定义一个长度为 amount+1 的数组 dp，其中 dp[i] 表示凑成金额 i 所需的最少硬币数量。

•   动态规划的状态转移方程为：
  

•   dp[i] = min(dp[i], dp[i - coin] + 1)，
  

•  其中 coin 表示硬币的面额，且 coin <= i
  

  这个方程的意思是，如果当前的金额 i 可以由硬币的面额 coin 和金额 i - coin 组成，那么 dp[i] 就可以通过 dp[i - coin] + 1 来更新，即将 coin 加入到凑成金额 i 的硬币组合中。

• 2、初始化数组dp，长度为amount + 1，全部初始化为amount + 1。

• 3、设置dp[0]为0，表示凑成金额0所需的最少硬币个数为0。

• 4、使用循环遍历从1到amount的每个金额i，内层循环遍历硬币数组coins，更新dp[i]为dp[i - coin] + 1和dp[i]中的较小值，其中coin为硬币的面额。

• 5、如果dp[amount]的值仍然为amount + 1，说明无法凑成总金额，返回-1，否则返回dp[amount]。

java实现

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

    public static void main(String[] args) {
        CoinChange cc = new CoinChange();
        int[] coins = {1, 2, 5};
        int amount = 11;
        System.out.println("Minimum number of coins: " + cc.coinChange(coins, amount)); // Output: 3 (11 = 5 + 5 + 1)
    }
}

时间空间复杂度

• 时间复杂度：外层循环遍历了amount次，内层循环遍历了硬币数组coins，时间复杂度为O(amount * coins.length)。

• 空间复杂度：使用了长度为amount + 1的数组dp，空间复杂度为O(amount)。