題解 | #換錢的最少貨幣數(shù)#
換錢的最少貨幣數(shù)
http://www.fangfengwang8.cn/practice/3911a20b3f8743058214ceaa099eeb45
dp[n] = min{dp[n], dp[n - arr[j]] + 1}
int max = aim + 1; int size = arr.length; int[] dp = new int[aim + 1]; Arrays.fill(dp, max); dp[0] = 0; for(int i = 1;i <= aim; i++) { for(int j = 0;j < size; j++){ if(arr[j] <= i) { dp[i] = Math.min(dp[i], dp[i - arr[j]] + 1); } } }
對(duì)于dp[n],不能找錢的情況有兩種
- 所有的arr[j],都大于n。這種情況下,dp[n]為設(shè)定的初始值
- 存在arr[j] < n,但對(duì)應(yīng)的dp[n - arr[j]]為設(shè)定的初始值,最終dp[n]也為初始值。
綜上,當(dāng)dp[n]為設(shè)定的初始值時(shí),說(shuō)明無(wú)法找錢。
故返回語(yǔ)句為:
return dp[aim] == max ? -1 : dp[aim];