动态规划算法。
dp[i][j]为：使用前i种硬币凑成j的方法数。dp[i][0]=1(凑成金额0，只能有一种方法，就是每种硬币0个)。
状态转移方程：dp[ i ][ j ] = dp[ i-1 ][ j ] + dp[ i ][ j - coins[ i ] ]
(1)用coins[ i ] : 用了coins[ i ]，那么金额还剩 j - coins[ i ]，用coins[ 1……i ]去凑金额 j - coins[ i ]。------------------->dp[ i ][ j - coins[ i ] ]
(2)不用coins[ i ] ：只用1……i-1个硬币。---------------------> dp[ i-1 ][ j ]
代码如下：
public static int change(int amount, int[] coins) { int[][] dp = new int[coins.length+1][amount+1]; for (int i = 0; i < dp.length; i++) { //金额为0,有一种方法（0个硬币）） dp[i][0] = 1; } //dp[i][j]为用coins[0~i]组成金额j一共有多少种组合方法 for (int i = 1; i <=coins.length ; i++) { for (int j = 1; j <=amount ; j++) { dp[i][j] = dp[i-1][j]; if(j>=coins[i-1]) { dp[i][j] =dp[i-1][j] + dp[i][j -coins[i-1]]; //0~i-1组成金额j有多少种组合 + 0~i组成金额为j-coins[i]有多少种组合 } } } return dp[coins.length][amount]; }
原文：https://www.cnblogs.com/yunn/p/13656041.html