问题：

给定一组硬币面值coins，和一个总价amount

求用给定面值硬币中，有多少种构成方法能构成总价。

Example 1:
Input: amount = 5, coins = [1, 2, 5]
Output: 4
Explanation: there are four ways to make up the amount:
5=5
5=2+2+1
5=2+1+1+1
5=1+1+1+1+1

Example 2:
Input: amount = 3, coins = [2]
Output: 0
Explanation: the amount of 3 cannot be made up just with coins of 2.

Example 3:
Input: amount = 10, coins = [10] 
Output: 1
 
Note:
You can assume that
0 <= amount <= 5000
1 <= coin <= 5000
the number of coins is less than 500
the answer is guaranteed to fit into signed 32-bit integer

　　

解法：DP(动态规划) Unbounded knapsack problem(完全背包问题)

1.确定【状态】：

• 可选择的元素：前 i 种硬币面值
• 和：amount

2.确定【选择】：

• 选择当前的硬币面值，作为最后一个硬币：coins[i]
• 不选择当前的硬币面值，作为最后一个硬币

3. dp[i][a]的含义：

前 i 个硬币面值中，构成总价值a的总构成方法数。

4. 状态转移：

dp[i][a]= SUM {

• 选择 coins[i]作为最后一个硬币：dp[i][a-coins[i]]：=前 i 种硬币中，可构成 a-最后一个硬币值coins[i] 的总构成方法数
• 不选择 coins[i]作为最后一个硬币：dp[i-1][a]：=前 i-1 种硬币中，可构成 a 的总构成方法数。

}

5. base case：

• dp[0][a]=0
• dp[i][0]=1

代码参考：

 1 class Solution {
 2 public:
 3     //dp[i][a]:the number of ways to get amount a from the first i types of coins.
 4     //case_1: select i-th type: dp[i][a-coins[i]]
 5     //case_2: don't select i-th type: dp[i-1][a]
 6     //dp[i][a] = case_1+case_2
 7     //base case:
 8     //dp[0][a]=0
 9     //dp[i][0]=1
10     int change(int amount, vector<int>& coins) {
11         vector<vector<int>> dp(coins.size()+1, vector<int>(amount+1, 0));
12         for(int i=0; i<=coins.size(); i++) {
13             dp[i][0] = 1;
14         }
15         for(int i=1; i<=coins.size(); i++) {
16             for(int a=1; a<=amount; a++) {
17                 if(a-coins[i-1]>=0) {
18                     dp[i][a] = dp[i][a-coins[i-1]] + dp[i-1][a];
19                 } else {
20                     dp[i][a] = dp[i-1][a];
21                 }
22             }
23         }
24         return dp[coins.size()][amount];
25     }
26 };

♻️ 优化：

空间复杂度：2维->1维

去掉 i 

压缩所有行到一行。

使用：本行修改过的前面的 a-coins[i-1]列 + 上一行的第a列（本列）

更新本行本列，可直接用 前面更新过的 a-coins[i-1]列元素 + 未更新的当前元素

代码参考：

 1 class Solution {
 2 public:
 3     //dp[i][a]:the number of ways to get amount a from the first i types of coins.
 4     //case_1: select i-th type: dp[i][a-coins[i]]
 5     //case_2: don't select i-th type: dp[i-1][a]
 6     //dp[i][a] = case_1+case_2
 7     //base case:
 8     //dp[0][a]=0
 9     //dp[i][0]=1
10     int change(int amount, vector<int>& coins) {
11         vector<int> dp(amount+1, 0);
12         dp[0] = 1;
13         for(int i=1; i<=coins.size(); i++) {
14             for(int a=1; a<=amount; a++) {
15                 if(a-coins[i-1]>=0) {
16                     dp[a] += dp[a-coins[i-1]];
17                 }
18             }
19         }
20         return dp[amount];
21     }
22 };