LeetCode 动态规划 coin change-白红宇

LeetCode 动态规划 coin change

阅读量：364 次

发布时间：2019-03-04

本文共 1314 字，大约阅读时间需要 4 分钟。

为了找到凑成给定总金额所需的最少硬币个数，我们可以使用动态规划的方法。以下是详细的解决方案：

动态规划方法

初始化数组：创建一个大小为 amount + 1 的数组 f，其中 f[i] 表示凑成金额 i 所需的最少硬币数。初始化所有元素为 Integer.MAX_VALUE，除了 f[0] 设为 0，因为凑成0元不需要任何硬币。

遍历金额：从1到 amount 逐一处理每个金额 i。

遍历硬币面额：对于每个金额 i，遍历所有硬币的面额 coins[j]。如果 i 大于或等于 coins[j]，则更新 f[i] 为 f[i - coins[j]] + 1 和当前 f[i] 中的较小值。

检查结果：最后，检查 f[amount] 是否仍然是 Integer.MAX_VALUE。如果是，说明无法凑成总金额，返回-1；否则，返回 f[amount]。

代码实现

public class CoinChange {
    public int minCoins(int[] coins, int amount) {
        int[] f = new int[amount + 1];
        for (int i = 0; i <= amount; i++) {
            f[i] = Integer.MAX_VALUE;
        }
        f[0] = 0;
        
        for (int i = 1; i <= amount; i++) {
            for (int j = 0; j < coins.length; j++) {
                if (i >= coins[j]) {
                    if (f[i - coins[j]] + 1 < f[i]) {
                        f[i] = f[i - coins[j]] + 1;
                    }
                }
            }
        }
        
        if (f[amount] == Integer.MAX_VALUE) {
            return -1;
        } else {
            return f[amount];
        }
    }
}

代码解释

初始化数组：数组 f 初始化为 Integer.MAX_VALUE，f[0] 设为 0，表示凑成0元不需要硬币。

遍历金额：外层循环从1到 amount，逐一处理每个金额。

遍历硬币：内层循环遍历每个硬币的面额，检查当前硬币是否可以用于凑成当前金额。

更新最少硬币数：如果当前硬币可用于凑成金额，更新 f[i] 为使用该硬币后的最少硬币数。

返回结果：检查最终结果，返回-1表示无法凑成，否则返回所需硬币数。

这种方法确保了每个金额的最优解，通过动态规划有效地分解问题，确保了最终结果的正确性。

转载地址：http://gdyg.baihongyu.com/

你可能感兴趣的文章