CoinChange { public static int coinChange2(int[] coins, int amount) { Arrays.sort(coins); int[] dp = new int[amount + 1]; for (int j = 0; j < coins.length; j++) { for (int i = 0; i < amount; i++) { if (i + 1 == coins[j]) { dp[i]++; } else if (i + 1 > coins[j]) { dp[i] += dp[i - coins[j]]; } } } for (int i = 0; i < amount; i++) { for (int j = 0; j < coins.length; j++) { if (i + 1 == coins[j]) { dp[i]++; } else if (i + 1 > coins[j]) { dp[i] += dp[i - coins[j]]; } System.out.printf("i + 1 = %d, coins[%d] = %d, dp[%d] = %d\n", i + 1, j, coins[j], i, dp[i]); } } return dp[amount - 1]; }  static int coinChange(int[] coins, int amount); static int coinChange2(int[] coins, int amount);  }
@Test(dataProvider = "change2Provider") public void test(int[] coins, int amount, int expectedWay){ assertEquals(CoinChange.coinChange2(coins, amount), expectedWay); }