网站负责人 备案,网站开发 后端服务,wordpress开发主题,泗洪建设局网站题目#xff1a;
给你一个整数数组coins,表示不同面额的硬币#xff1b;以及一个整数amount,表示总金额。 计算并返回可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额#xff0c;返回-1。 你可以认为每种硬币的数量是无限的。
示例1#xff1…题目
给你一个整数数组coins,表示不同面额的硬币以及一个整数amount,表示总金额。 计算并返回可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额返回-1。 你可以认为每种硬币的数量是无限的。
示例1 输入coins[1,2,5],amount11 输出3 解释11551
思路
动态规划
代码 public int coinChange(int[] coins, int amount) {if (coins null || coins.length 0) {return -1;}// memo[n]的值 表示的凑成总金额为n所需的最少的硬币个数int[] memo new int[amount1];//设置初始值Arrays.fill( memo, amount1);memo[0] 0;//i是要凑够的金额for (int i1; i amount; i) {for (int j0; j coins.length; j) {//如果硬币值没有超过所需金额if (i- coins[j] 0) {// memo[i]有两种实现的方式,//一种是包含当前 coins[i] 剩余的钱就是 i-coins[i].要兑换的硬币数是 memo[i-coins[j]] 1这个1其实就是多一个硬币 coins[i] 。//另一种就是不包含要兑换的硬币数是 memo[i]memo[i] Math.min ( memo[i] , memo[ i-coins[j]] 1);}} }return memo[amount] (amount1) ? -1 : memo[amount];}
