其中，dp[i][j]表示使用前i个硬币可以凑出总价值为j的钱数的最小硬币数，初始化时将dp[0][i]的值设为无穷大，因为凑出总价值为0的钱数不需要任何硬币。在状态转移方程中，如果j < coins[i - 1]，则不能选当前硬币，此时dp[i][j] = dp[i - 1][j]；否则，可以选当前硬币，dp[i][j] = dp[i][j - coins[i - 1]] + 1。最后，如果dp[coins.length][amount]的值为无穷大，则无法凑出总价值为amount的钱数，否则返回dp[coins.length][amount]的值。
注意：当对dp[0][*]这一行数据进行初始化时候，应该初始化为一个较大的数，但是不能用Integer.MAX_VALUE，否则后续对Integer.MAX_VALUE进行加操作时候，溢出为很小的负数。因此在此处选取amount+1进行初始化。（amount+1一定大于最终的硬币数量）
class Solution {
public int coinChange(int[] coins, int amount) {
int[][] dp = new int[coins.length + 1][amount + 1];
for (int i = 1; i <= amount; i++) {
dp[0][i] = amount+1;
}
for (int i = 1; i <= coins.length; i++) {
for (int j = 1; j <= amount; j++) {
if (j < coins[i - 1]) {
dp[i][j] = dp[i - 1][j];
} else {
dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - coins[i - 1]] + 1);
}
}
}
return dp[coins.length][amount] == amount+1 ? -1 : dp[coins.length][amount];
}
}
参考:
作者：flix
链接：https://leetcode.cn/problems/coin-change/solutions/1412324/by-flix-su7s/