零钱兑换--动态规划_兑换硬币 c语言 动态规划

零钱兑换–动态规划

class Solution {
    public int coinChange(int[] coins, int amount) {
        /*
        动态规划题解的特点：最小 最大 求最值 计算数量等等
        边界条件  状态  选择  递归方程 
        与递归的区别 递归重复计算耗费不必要的计算上   动态规划利用数组减少了重复计算
        动态规划：特点 整体最优解 包含了局部最优解
        重叠子问题： 我们求11 元的最优解相当于求
        min(11-5,11-2,11-1)三个当中的最优解 
        我们定义一个最优解的数组 长度为 amount+1  定义为总金额为amount
        所需要的最少的硬币数量
        如果我们凑不成该金额的硬币数 那么我们就将这个值设为正无穷，意思是我们没有办法在给定的硬币中选出一些来
        凑出这个金额
        地推公式
        f[11] = min{f[11-2]+1,f[11-1]+1,f[11-5]+1}当中取最小值
        求总金额为11 所需要的最小硬币数量 = min {金额为11-2所需要的最小数量 +1，金额为11-1所需要的最小数量 +1，金额为11-5所需         要的最小数量 +1} 三者取最小
        */
        int  f[]= new int[amount+1];     //凑出金额为amount 的所需要的硬币数量
        f[0]= 0 ;//边界条件 金额为0 的时候所需要的硬币为0 个
                 //注意 当金额f[i]的 i<0的时候，也就是我们没有办法拼出总金额为负数的硬币 应该设为正无穷枚硬币拼出
        for(int i = 1; i< f.length; i++){
            f[i] = Integer.MAX_VALUE;   //初始化In设置为无法拼出该金额
                     //遍历硬币的数组看看是否能拼出  金额-coins[j] 的 最小值
            for(int j = 0 ; j  <  coins.length ; j++){
                if(i-coins[j]>=0  && f[i-coins[j]] !=Integer.MAX_VALUE ){
                        //这里的条件判断是细节重点  1.拼出的金额一定要大于等于0  2.我们的子问题不能是无法拼出的 也就是值不能为
                         //Integer.MAX_VALUE; 因为下一步比较的时候+1 会越界整数范围的
                    f[i] = Math.min(f[i],f[i-coins[j]]+1);
                }
            }
        }
        if(f[amount]== Integer.MAX_VALUE){
            return -1;
        }else{
            return f[amount];
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38