目录
1、题目2、思路、二维c++代码4、二维java代码5、一维优化6、一维c++代码7、一维java代码
1、题目
给你一个整数数组coins表示不同面额的硬币，另给一个整数amount表示总金额。
请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额，返回0。
假设每一种面额的硬币有无限个。
题目数据保证结果符合2位带符号整数。
示例1：
输入：amount=5,coins=[1,2,5]输出：4解释：有四种方式可以凑成总金额：5=55=2+2+15=2+1+1+15=1+1+1+1+1
示例2：
输入：amount=,coins=[2]输出：0解释：只用面额2的硬币不能凑成总金额。
示例：
输入：amount=10,coins=[10]输出：1
提示：
1=coins.length==coins=coins中的所有值互不相同0=amount=
2、思路
(动态规划，完全背包)
二维分析
状态表示：f[j]表示从前i种硬币中选，且总金额恰好为j的所有选法集合的方案数。
那么f[n][amount]就表示表示从前n种硬币中选，且总金额恰好为amount的所有选法集合的方案数，即为答案。
集合划分：
按照第i种硬币可以选0个,1个，2个，个，，，，k个划分集合f[j]。其中k*coin=j，也就是说在背包能装下的情况下，枚举第i种硬币可以选择几个。
第i种硬币选0个，f[j]=f[i-1][j]第i种硬币选1个，f[j]=f[i-1][j-coins]第i种硬币选k个，f[j]=f[i-1][j-k*coins]
状态计算：
f[j]=f[i-1][j]+f[i-1][j-coins]+f[i-1][j-2*coins],,,,,,+f[i-1][j-k*coins]。初始化条件：
f[0][0]=1，使用0种硬币币，凑0元钱，也是一种方案。
时间复杂度分析：O(amount2n)O(amount^2*n)O(amount2n)，其中amountamountamount是总金额，nnn是数组coinscoinscoins的长度。
、二维c++代码
classSolution{public:intchange(intamount,vectorintcoins){intn=coins.size();vectorvectorintf(n+1,vectorint(amount+1,0));f[0][0]=1;//使用0种货币，凑0元钱,也是一种方案for(inti=1;i=n;i++){intv=coins[i-1];for(intj=0;j=amount;j++)for(intk=0;k*v=j;k++)f[j]+=f[i-1][j-k*v];//状态计算方程}turnf[n][amount];}};
4、二维java代码
classSolution{publicintchange(intamount,int[]coins){intn=coins.length;int[][]f=newint[n+1][amount+1];f[0][0]=1;//使用0种货币，凑0元钱,也是一种方案for(inti=1;i=n;i++){intv=coins[i-1];for(intj=0;j=amount;j++)for(intk=0;k*v=j;k++)f[j]+=f[i-1][j-k*v];//状态计算方程}turnf[n][amount];}}
5、一维优化
二维完全背包求解方案时间复杂度较高，考虑一维优化。
v代表第i种硬币的面值
f[j]=f[i-1][j]+f[i-1][j-v]+f[i-1][j-2v]+,,,,,+f[i-1][j-kv])
f[j-v]=f[i-1,[j-v]+f[i-1][j-2v]+,,,,,+f[i-1][j-kv])
因此：
f[j]=f[i-1][j]+f[j-v])
图示：
去掉物品种类维度，状态计算方程为：f[j]=f[j]+f[j-v]
时间复杂度分析：O(amountn)O(amount*n)O(amountn)，其中amountamountamount是总金额，nnn是数组coinscoinscoins的长度。
6、一维c++代码
classSolution{public:intchange(intamount,vectorintcoins){vectorintf(amount+1);f[0]=1;//f[0][0]=1;for(inti=1;i=coins.size();i++){intv=coins[i-1];for(intj=v;j=amount;j++)f[j]+=f[j-v];}turnf[amount];}};
7、一维java代码
classSolution{publicintchange(intamount,int[]coins){int[]f=newint[amount+1];f[0]=1;//f[0][0]=1;for(inti=1;i=coins.length;i++){intv=coins[i-1];for(intj=v;j=amount;j++)f[j]+=f[j-v];}turnf[amount];}}
原题链接：.零钱兑换II
,