动态规划—零钱兑换_动态规划零钱兑换

leetcode地址：322. 零钱兑换

问题描述：

给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。你可以认为每种硬币的数量是无限的。比如coins = [1,2,5],amount = 11,11 = 5 + 5 + 1，最终结果为3

算法思路：

本题可以采用动态规划思路，也可以采用贪心算法思路，此篇文章讲解动态规划如何做。首先看下记忆搜索的方式

可以看出在进行递归的时候，有很多重复的节点要进行操作，这样会浪费很多的时间。使用数组memo[ ] 来保存节点的值。memo[n]表示钱币 n 可以被换取的最少的硬币数，不能换取就为 -1。findWay 函数的目的是为了找到 amount 数量的零钱可以兑换的最少硬币数量，返回其值 int在进行递归的时候，memo[n]被复制了，就不用继续递归了，可以直接的调用。

2. 动态规划

上面的记忆化搜索是先从 memo[amonut-1]开始，从上到下，而动态规划从 memo[0]开始，从下到上

class Solution {
    public int coinChange(int[] coins, int amount) {
        // 自底向上的动态规划
        if(coins.length == 0){
            return -1;
        }
 
        // memo[n]的值： 表示的凑成总金额为n所需的最少的硬币个数
        int[] memo = new int[amount+1];
        memo[0] = 0;
        for(int i = 1; i <= amount;i++){
            int min = Integer.MAX_VALUE;
            for(int j = 0;j < coins.length;j++){
                if(i - coins[j] >= 0 && memo[i-coins[j]] < min){
                    min = memo[i-coins[j]] + 1;
                }
            }
            memo[i] = min;
        }
 
        return memo[amount] == Integer.MAX_VALUE ? -1 : memo[amount];
    }
}

最重要的是下面这段代码：

if(i - coins[j] >= 0 && memo[i-coins[j]] < min){
    min = memo[i-coins[j]] + 1;
}

思考一下两个问题：

1）为什么采用 i-coins[j] 和memo[i-coins[j]]进行判断呢？

i-coins[j] 代表 当前金额减去一次面额后的金额是多少，memo[i-coins[j]]代表减去一次面额后的金额的最小兑换次数

2）为什么要判断memo[i-coins[j]] < min？

如果比当前金额小的金额兑换次数更多的话，则不需要重置min的值