办网站需要多少费用,哪个网站做ppt好,现在建设一个网站还能够赚钱吗,青岛专业网站开发公司给你一个整数数组 coins #xff0c;表示不同面额的硬币#xff1b;以及一个整数 amount #xff0c;表示总金额。
计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额#xff0c;返回 -1 。
你可以认为每种硬币的数量是无限的。 示…
给你一个整数数组 coins 表示不同面额的硬币以及一个整数 amount 表示总金额。
计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额返回 -1 。
你可以认为每种硬币的数量是无限的。 示例 1
输入coins [1, 2, 5]amount 11输出3解释11 5 5 1
示例 2
输入coins [2]amount 3输出-1思想动态规划
边界条件dp[0] 0
状态转移方程F(i) min j0,1...nF(i-cj) 1
定义 F(i)为组成金额 i所需最少的硬币数量假设在计算 F(i) 之前我们已经计算出 F(0) ~F(i−1)
的答案其中 cj代表的是第 j枚硬币的面值
代码
class Solution {public int coinChange(int[] coins, int amount) {// 初始化动态规划数组 初始化最大值数组int max amount 1;int[] dp new int[amount 1]; // 数组长度最大为amount1的原因为 最坏情况amount 11...1// 动态规划数组中填充最大值Arrays.fill(dp,max);dp[0] 0;// 从1开始遍历目标数值for(int i 1; i amount; i){// 遍历整数数字coins 判断数组中当前面面值是否能组成amountfor(int j 0; j coins.length; j){// 如果当前数组中面值小于i 进行递归计算 动态规划方程if(coins[j] i){dp[i] Math.min(dp[i], dp[i - coins[j]] 1) ;}}}return dp[amount] amount ? -1 : dp[amount];}
}
