北京建设注册中心网站,wordpress整合教程,制作网站公,线上营销方案文章目录题目描述思路 代码题目描述
和完全平方数基本上一样啦#xff0c;但是我觉得这道题的判断 循环处理更恶心
思路 代码
相对于完全平方数#xff0c;这里要考虑零钱数组无序#xff0c;要先进行排序与此同时#xff0c;还要考虑零钱数组的值并…
文章目录题目描述思路 代码题目描述
和完全平方数基本上一样啦但是我觉得这道题的判断 循环处理更恶心
思路 代码
相对于完全平方数这里要考虑零钱数组无序要先进行排序与此同时还要考虑零钱数组的值并不一定最小为1因此 dp[i] 不能直接初始化为 i用到临时变量 min结合对比判断 防止dp[i] 变成 MIN_VALUE而非直接Math.min()
class Solution {/*** 感觉和平方数很像*/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];}
}无注释版
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];}
}
