[数据结构与算法]leetcode第322题零钱兑换

给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。
计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。
你可以认为每种硬币的数量是无限的。

思路

背包问题。

动规分析如下：

1确定dp数组以及下标的含义

dp[i]=凑足总额为j所需钱币的最少个数为dp[i]

2确定递推公式

得到dp[i]（考虑coins[j]），只有一个来源，dp[i]- coins[j]]（没有考虑coins[j]）。

凑足总额为i - coins[j]的最少个数为dp[i - coins[j]]，那么只需要加上一个钱币coins[j]即dp[i - coins[j]] + 1就是dp[i]（考虑coins[j]）

所以dp[i] 要取所有 dp[i - coins[j]] + 1 中最小的。

递推公式：dp[i] = min(dp[i - coins[j]] + 1, dp[i]);

3dp数组如何初始化

首先凑足总金额为0所需钱币的个数一定是0，那么dp[0] = 0;

其他下标对应的数值呢？

考虑到递推公式的特性，dp[j]必须初始化为一个最大的数，否则就会在min(dp[i - coins[j]] + 1, dp[i])比较的过程中被初始值覆盖。

所以下标非0的元素都是应该是最大值。

4确定遍历顺序

外层for循环遍历物品，内层for遍历背包或者外层for遍历背包，内层for循环遍历物品都是可以的！

C++代码

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        //dp[i]=凑到i块钱所需要的最小硬币数
        vector<int> dp(amount+1,INT_MAX);
        //初始条件：凑到0块钱需要0枚硬币
        dp[0]=0;
        for(int i=1;i<=amount;i++)
        {
            for(int j=0;j<coins.size();j++)
            {
                //保证不越界而且前面的值已经更新过
                if(i-coins[j]>=0&&dp[i-coins[j]]!=INT_MAX)
                //取较小值
                    dp[i]=min(dp[i],dp[i-coins[j]]+1);
            }
        }
        if(dp[amount]==INT_MAX)
            return -1;
        return dp[amount];
    }
};