网站建设与百度推广,普通网站 用多说,桥南做网站,扬中论坛全部帖子322. 零钱兑换 原题链接#xff1a;完成情况#xff1a;一开始错误原因 解题思路#xff1a;参考代码#xff1a;__322 零钱兑换__错误思路还得是dp去做 原题链接#xff1a;
零钱兑换
完成情况#xff1a;
一开始错误 原因 /*解题思路#xff1a;1.先sort一下coins… 322. 零钱兑换 原题链接完成情况一开始错误原因 解题思路参考代码__322 零钱兑换__错误思路还得是dp去做 原题链接
零钱兑换
完成情况
一开始错误 原因 /*解题思路1.先sort一下coins确保硬币面值是从小到大排序的2.从最大面额的硬币开始到最小面额的硬币来结束程序 - for3.每次面额从1开始往最多可以选择的能力去这会导致一个很大的问题那就是原本可以找的开的零钱会因为你上述的操作导致根本找不开因为不存在最低基本单位1*/解题思路 参考代码
__322 零钱兑换__错误思路
package 西湖算法题解___中等题;import java.util.Arrays;public class __322 零钱兑换__错误思路 {public static void main(String[] args) {int coins[] {186,419,83,408};int amount 6249;System.out.println(coinChange(coins,amount));}public static int coinChange(int[] coins, int amount) {/*解题思路1.先sort一下coins确保硬币面值是从小到大排序的2.从最大面额的硬币开始到最小面额的硬币来结束程序 - for3.每次面额从1开始往最多可以选择的能力去这会导致一个很大的问题那就是原本可以找的开的零钱会因为你上述的操作导致根本找不开因为不存在最低基本单位1*/Arrays.sort(coins);int useNums 0;//先过滤掉一些没用的//如果总金额小于最小的硬币面值if (amount0){return 0;}int coins_length coins.length -1;for (int icoins_length;i0;i--){//所有硬币的面值for (int j1;jamount/coins[i]1;j){if (amount - coins[i]*j 0){//继续useNums;} else if (amount - coins[i]*j 0) {useNums;return useNums;}else{//说明当前面值换不了了amount-(coins[i]*(j-1));break;}}}return -1;}
}
还得是dp去做
package 西湖算法题解___中等题;import java.util.Arrays;public class __322零钱兑换__动态递归 {public int coinChange(int[] coins, int amount) {int max amount 1;int dp_coins [] new int[amount 1];Arrays.fill(dp_coins,max);dp_coins[0] 0;for (int i1;iamount;i){for (int j0;icoins.length;j){if (coins[j] i){dp_coins[i] Math.min(dp_coins[i],dp_coins[i - coins[j]] 1);}}}return dp_coins[amount] amount ? -1 :dp_coins[amount];}
}
