一：解题思路
运用动态规划的思想去解题。定义状态d(i,j)表示使用前i种面值的硬币(即面值数组中0~i-1的元素)，凑成数值j的组合数量。
初始条件：d(0,j)=0，d(i,0)=1
状态转移方程：d(i,j)=d(i-1,j)+d(i,j-c[i-1])，其中，j-c[i-1]>=0，d表示二维数组。d(n,sum)
Time:O(n*sum)，Space:O(n*sum)
二：完整代码示例 (C、C++、Java、Python)
方法一C++:
class Solution { public: int change(int amount, vector<int>& coins) { vector<vector<int>> d(coins.size()+1,vector<int>(amount+1,0)); for (int i = 0; i <= coins.size(); i++) d[i][0] = 1; for (int i = 1; i <= coins.size(); i++) { for (int j = 1; j <= amount; j++) { int useCurCoin = j >= coins[i - 1] ? d[i][j - coins[i - 1]] : 0; d[i][j] = d[i - 1][j] + useCurCoin; } } return d[coins.size()][amount]; } };
方法一Java:
class Solution { public int change(int amount, int[] coins) { int[][] d=new int[coins.length+1][amount+1]; for (int i=0;i<=coins.length;i++) d[i][0]=1; for (int i=1;i<=coins.length;i++){ for (int j=1;j<=amount;j++){ int useCurCoin=(j>=coins[i-1])?d[i][j-coins[i-1]]:0; d[i][j]=d[i-1][j]+useCurCoin; } } return d[coins.length][amount]; } }
方法一Python:
class Solution: def change(self, amount: int, coins: List[int]) -> int: d=[[0]*(amount+1) for i in range(len(coins)+1)] for i in range(0,len(coins)+1): d[i][0]=1 for i in range(1, len(coins)+1): for j in range(1,amount+1): if j>=coins[i-1]: useCurCion=d[i][j-coins[i-1]] else: useCurCion=0 d[i][j]=d[i-1][j]+useCurCion return d[len(coins)][amount]
原文：https://www.cnblogs.com/repinkply/p/14606771.html