public int change(int amount, int[] coins) {

int[][] dp = new int[coins.length+1][amount + 1];

dp[0][0] = 1;

for (int i=1; i<=coins.length; i++) {

dp[i][0] = 1;

int c = coins[i-1];

for (int j=1; j<=amount; j++) {

dp[i][j] = dp[i-1][j] + (j < c ? 0 : dp[i][j-c]);

}

}

return dp[coins.length][amount];

}

public int change2(int amount, int[] coins) {

int[] dp = new int[amount + 1];

dp[0] = 1;

for (int coin : coins) {

for (int i = coin; i <= amount; i++) {

dp[i] += dp[i-coin];

}

}

return dp[amount];

}

public int change3(int amount, int[] coins) {

int[][] dp = new int[coins.length+1][amount + 1];

for (int i=0; i<=coins.length; i++) dp[i][0] = 1;

for (int j=1; j<=amount; j++) {

for (int i=1; i<=coins.length; i++) {

int c = coins[i - 1];

dp[i][j] = dp[i-1][j] + (j < c ? 0 : dp[i][j-c]);

}

}

return dp[coins.length][amount];

}