DP: 518. Coin Change 2 Java

DP最重要的就是一些初始化的條件預設

及 一個想法 就是去查詢之前的答案 是否有更好的解答(但是DP 有很多形式 不一定是這句的"更好解答",總之就是要查表,或是一種拿與不拿的問題)

Input: amount = 5, coins = [1, 2, 5]
Output: 4
Explanation: there are four ways to make up the amount:
5=5
5=2+2+1
5=2+1+1+1
5=1+1+1+1+1

DP解

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;
for (int j = 1; j <= amount; j++) { // j 就是錢的金額
dp[i][j] = dp[i-1][j] + (j >= coins[i-1] ? dp[i][j-coins[i-1]] : 0); //後面的意思就是說拿這個硬幣並去查表之前的金額有幾種把它加進來
}
}
return dp[coins.length][amount];

後來有更簡便的寫法 原因如下!

Now we can see that dp[i][j] only rely on dp[i-1][j] and dp[i][j-coins[i]], then we can optimize the space by only using one-dimension array.

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];
//dp[i] = dp[i] + dp[i-coin];
}
}
return dp[amount];

快學會DP啊!!