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

零钱兑换–动态规划

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];        }    }}