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

零钱兑换问题 I

1、题目：力扣原题

2、分析

（1）结合我们之前分析的（动态规划解决背包问题），这里硬币有无限个对应完全背包问题。但又存在一点区别：纯完全背包是能否凑成总的金额，本题是要求凑成总金额的组合个数。

（2）要注意是求解组合 还是排列 问题。例如 221 和121可以表示一种组合或者两种排列。组合之间不强调元素之间的顺序，而排列强调元素之间的顺序。

DP五部曲分析如下：

1）确定dp含义

        dp[j]: 表示凑成总金额j可以得到的货币组合总数；

2）确定递推公式‘’

        dp[j] （考虑coins[i]的组合总和） 就是所有的dp[j - coins[i]]（不考虑coins[i]）相加。

        所以递推公式：dp[j] += dp[j - coins[i]];

（求装满背包有几种方法，一般公式都是：dp[j] += dp[j - nums[i]];）

3）初始化

        dp[0]=1,表示凑成金额为0的货币组合数为1；

4）确定遍历顺序

        这里就要根据上面讨论的来进行区别，题目是要求组合数还是排列数需要对遍历顺序进行处理。因为纯完全背包求得是能否凑成总和，和凑成总和的元素有没有顺序没关系，即：有顺序也行，没有顺序也行！

        而本题要求凑成总和的组合数，元素之间要求没有顺序。所以纯完全背包是能凑成总和就行，不用管怎么凑的。本题是求凑出来的方案个数，且每个方案个数是为组合数。那么本题，两个for循环的先后顺序可就有说法了。

        为了清晰对比，我们对两个for循环的先后遍历顺序讨论一下:

a、外层for循环遍历钱币，