校园服装网站建设演示文稿,郑州商城网站设计,网站二级目录是什么,网上创建公司Leetcode 322. 零钱兑换#xff08;完全背包#xff09;题目 给你一个整数数组 coins #xff0c;表示不同面额的硬币#xff1b;以及一个整数 amount #xff0c;表示总金额。计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额完全背包题目 给你一个整数数组 coins 表示不同面额的硬币以及一个整数 amount 表示总金额。计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额返回 -1 。你可以认为每种硬币的数量是无限的。1 coins.length 121 coins[i] 2^31 - 10 amount 10^4 解法 动态规划之完全背包定义一维数组 dp其中 dp[i] 表示组成总金额 i 所需的最少硬币数初始化 dp 数组dp[0] 为 0表示组成金额 0 需要 0 个硬币dp[1…amount] 初始化为极大值表示当前无法组成该总金额遍历硬币数组 coins对于每种面额的硬币遍历总金额范围内可以添加该硬币的金额下标。即 dp[j] 不为极大值说明可以组成 j coins[i] 金额此时转移方程为dp[j coins[i]] Math.min(dp[j coins[i]], dp[j] 1)遍历结束后dp[amount] 如果仍为极大值则无法组成返回 -1否则返回 dp[amount] 表示最少需要的硬币数PS由于 amount 最多由 amount 个硬币组成因此初始化极大值只要大于 amount 就可以 代码 /*** 动态规划之完全背包* 定义一维数组 dp其中 dp[i] 表示组成总金额 i 所需的最少硬币数* 初始化 dp 数组dp[0] 为 0表示组成金额 0 需要 0 个硬币dp[1...amount] 初始化为极大值表示当前无法组成该总金额* 遍历硬币数组 coins对于每种面额的硬币遍历总金额范围内可以添加该硬币的金额下标。即 dp[j] 不为极大值说明可以组成 j coins[i] 金额此时转移方程为dp[j coins[i]] Math.min(dp[j coins[i]], dp[j] 1)* 遍历结束后dp[amount] 如果仍为极大值则无法组成返回 -1否则返回 dp[amount] 表示最少需要的硬币数* PS由于 amount 最多由 amount 个硬币组成因此初始化极大值只要大于 amount 就可以*/private static int solution(int[] coins, int amount) {// 判空if (amount 0) {return 0;}if (coins null || coins.length 0) {return -1;}// 定义且初始化 dp 数组int[] dp new int[amount 1];Arrays.fill(dp, 1, dp.length, Integer.MAX_VALUE);// 循环添加每一种硬币int coinsLen coins.length;int dpLen dp.length;for (int i 0; i coinsLen; i) {for (int j 0; j dpLen - coins[i]; j) {if (dp[j] Integer.MAX_VALUE) {dp[j coins[i]] Math.min(dp[j coins[i]], dp[j] 1);}}}return dp[amount] Integer.MAX_VALUE ? -1 : dp[amount];}
