322. 零钱兑换

LeetCode_322

题目描述

题解分析

我们采用自下而上的方式进行思考。仍定义 \(F(i)\) 为组成金额 i 所需最少的硬币数量，假设在计算 \(F(i)\) 之前，我们已经计算出 \(F(0)-F(i-1)\) 的答案。 则 \(F(i)\) 对应的转移方程应为

其中 \(c_j\) 代表的是第 j 枚硬币的面值，即我们枚举最后一枚硬币面额是 \(c_j\) ，那么需要从 \(i-c_j\) 这个金额的状态 \(F(i-c_j)\) 转移过来，再算上枚举的这枚硬币数量 1 的贡献，由于要硬币数量最少，所以 \(F(i)\)为前面能转移过来的状态的最小值加上枚举的硬币数量 1 。

代码实现

class Solution {
    public int coinChange(int[] coins, int amount) {
        //类似于完全背包的最终优化解法
        //dp[i]表示组成i金额所需的最少硬币数
        //dp[i] = Math.min(dp[i], dp[i-coins[j]]) + 1;
        int[] dp = new int[amount+1];
        Arrays.fill(dp, amount + 1);//为dp数组填充一个最大值，因为最小的面值为1元，所以最终最多的硬币数一定在amount之内
        dp[0] = 0;
        for(int i=1; i<=amount; i++){
            for(int j=0; j<coins.length; j++){
                if(i >= coins[j]){
                    dp[i] = Math.min(dp[i], dp[i-coins[j]] + 1);
                }
            }
        }
        return dp[amount] > amount ? -1 : dp[amount];
    }
}

322. 零钱兑换 + 动态规划 + 完全背包 + 硬币问题

原文：https://www.cnblogs.com/GarrettWale/p/14615058.html