给你一个整数数组 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示例 2：
输入：amount = 3, coins = [2]
输出：0
解释：只用面额 2 的硬币不能凑成总金额 3 。示例 3：
输入：amount = 10, coins = [10]
输出：1提示：
1 <= coins.length <= 3001 <= coins[i] <= 5000coins中的所有值 互不相同0 <= amount <= 5000
解题思路
状态表示
这道题比 322. 零钱兑换 还简单！很明显这就是一个完全背包问题，其中硬币就是物品，硬币的金额就是体积，背包体积就是总金额！
所以根据 “经验 + 题目要求”，可以得到 dp[i][j] 表示在前 i 个硬币中选，总金额正好等于 j，此时一共有多少种硬币组合。
状态转移方程
初始化
因为题目说如果任何硬币组合都无法凑出总金额，返回 0，所以只需要将第一行初始化为 0 即可，而这个步骤我们直接通过创建 dp 表的时候进行初始化即可。
但是因为第一个元素表示的是没有硬币可以选，但是背包空间为 0，相当于可以满足背包空间了，所以是一种硬币组合，所以 dp[0][0] 初始化为 1。
遍历顺序
从上往下，从左往右遍历。
返回值
根据状态表示，返回的就是最后一个位置 dp[n][amount]。
class Solution {
public:
int change(int amount, vector<int>& coins) {
// 创建dp表，dp[i][j]表示在前i个硬币中选，总金额正好等于j，此时的硬币组合数
int n = coins.size();
vector<vector<int>> dp(n + 1, vector<int>(amount + 1));
// 初始化
dp[0][0] = 1;
// 从上往下，从左往右遍历
for(int i = 1; i <= n; ++i)
{
for(int j = 0; j <= amount; ++j)
{
dp[i][j] = dp[i - 1][j];
if(j >= coins[i - 1])
dp[i][j] += dp[i][j - coins[i - 1]];
}
}
return dp[n][amount];
}
};优化
所有的「背包问题」，都可以进行空间上的优化。
对于 完全背包 类型的，我们的优化策略是：
- 删掉第一维
class Solution {
public:
int change(int amount, vector<int>& coins) {
// 创建dp表
int n = coins.size();
vector<int> dp(amount + 1);
// 初始化
dp[0] = 1;
// 从上往下，从左往右遍历
for(int i = 1; i <= n; ++i)
for(int j = coins[i - 1]; j <= amount; ++j)
dp[j] += dp[j - coins[i - 1]];
return dp[amount];
}
};