文章目錄

• 題目描述
• 思路 & 代碼

題目描述

• 和完全平方數(shù)基本上一樣啦，但是我覺(jué)得這道題的判斷 & 循環(huán)處理更惡心
  

思路 & 代碼

• 相對(duì)于完全平方數(shù)，這里要考慮零錢數(shù)組無(wú)序，要先進(jìn)行排序
• 與此同時(shí)，還要考慮零錢數(shù)組的值并不一定最小為1，因此 dp[i] 不能直接初始化為 i
• 用到臨時(shí)變量 min，結(jié)合對(duì)比判斷 防止dp[i] 變成 MIN_VALUE（而非直接Math.min()）

class Solution {/*** 感覺(jué)和平方數(shù)很像*/public int coinChange(int[] coins, int amount) {// 先排序Arrays.sort(coins);int[] dp = new int[amount + 1];for(int i = 1; i <= amount; i++){// 初始化int min = Integer.MAX_VALUE;for(int j = 0; j < coins.length && i - coins[j] >= 0; j++){// 很重要的判斷if(dp[i - coins[j]] < min){min = dp[i - coins[j]] + 1;}}dp[i] = min;}if(dp[amount] == Integer.MAX_VALUE){return -1;}return dp[amount];} }

• 無(wú)注釋版

class Solution {public int coinChange(int[] coins, int amount) {Arrays.sort(coins);int[] ans = new int[amount + 1];for(int i = 1; i <= amount; i++) {int min = Integer.MAX_VALUE;for(int j = 0; j < coins.length && i - coins[j] >= 0; j++) {if(ans[i - coins[j]] < min) {min = ans[i - coins[j]] + 1;}}ans[i] = min;}return ans[amount] == Integer.MAX_VALUE ? -1 : ans[amount];} }

總結(jié)

以上是生活随笔為你收集整理的【LeetCode笔记】322. 零钱兑换（Java、动态规划）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。