题目
给你一个整数数组 coins 表示不同面额的硬币，另给一个整数 amount 表示总金额。请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额，返回?0 。?
假设每一种面额的硬币有无限个。? 题目数据保证结果符合 32 位带符号整数。?
示例 1：
输入：amount = 5, coins =?[1, 2, 5]?
输出：4
解释：有四种方式可以凑成总金额：?
5=5?
5=2+2+1?
5=2+1+1+1?
5=1+1+1+1+1
https://leetcode-cn.com/problems/coin-change-2/
分析
这道题如果没想明白怎么才算是增加一种组合就是困难级别，如果想明白了就是简单级别。
按题目要求是需要排重的，如：1+1+2、 1+2+1、 1+1+2 这三种情况属于相同组合，这个排重要求对我造成了很大的困扰，促使我放弃了动态规划而选择贪心算法，因为对coins排序后贪心算法可以规避排重问题，但后来发现贪心算法的路越走越黑。
回到动态规划上，首先状态数组很容易定义：
int[] dp = new int[amount+1];困难点就在于如何定义状态方程了！?我们需要对状态方程每个下标都赋值，同时金币也是一个数组，所以这里有两层遍历。
如果先对状态数组遍历，则会面对排重问题，但如果先对金币数组遍历，则可以规避排重。
代码
class Solution {public int change(int amount, int[] coins) {????????int[] dp = new int[amount+1];????????dp[0] = 1;????????for(int?i=0;i<coins.length;i++){???????? for(int j=coins[i];j<=amount;j++){???????? dp[j] += dp[j-coins[i]];???????? }????????}????????return dp[amount];}}
结果
关注个人微信公众号：肌肉码农，回复“好友”讨论问题。