网站地图什么意思,电子商务营销推广,Audiology wordpress,高端品牌网站建设内容题目描述
给你一个整数数组 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
示例 3
输入coins [1], amount 0
输出0
解题思路 1.贪心 1.1 想要总硬币数最少肯定是优先用大面值硬币所以对 coins 按从大到小排序 先丢大硬币再丢会超过总额时就可以递归下一层丢的是稍小面值的硬币 2. 乘法对加法的加速 2.1 优先丢大硬币进去尝试也没必要一个一个丢可以用乘法算一下最多能丢几个 k amount / coins[c_index] 计算最大能投几个 amount - k * coins[c_index] 减去扔了 k 个硬币 count k 加 k 个硬币 如果因为丢多了导致最后无法凑出总额再回溯减少大硬币数量 3. 最先找到的并不是最优解 3.1 注意不是现实中发行的硬币面值组合规划合理会有奇葩情况 考虑到有 [1,7,10] 这种用例按照贪心思路 10 1 1 1 1 会比 7 7 更早找到 所以还是需要把所有情况都递归完 4. ans 疯狂剪枝 4.1 贪心虽然得不到最优解但也不是没用的 我们快速算出一个贪心的 ans 之后虽然还会有奇葩情况但是绝大部分普通情况就可以疯狂剪枝了 复杂度分析 时间复杂度O(Sn)其中 S是金额n是面额数。我们一共需要计算 S个状态的答案且每个状态 F(S)由于上面的记忆化的措施只计算了一次而计算一个状态的答案需要枚举 n个面额值所以一共需要 O(Sn)的时间复杂度。 空间复杂度O(S)我们需要额外开一个长为 S 的数组来存储计算出来的答案 F(S)。 代码
void coinChange(vectorint coins, int amount, int c_index, int count, int ans) {if (amount 0) {ans min(ans, count);return;}if (c_index coins.size()) return;for (int k amount / coins[c_index]; k 0 k count ans; k--) {coinChange(coins, amount - k * coins[c_index], c_index 1, count k, ans);}
}int coinChange(vectorint coins, int amount) {if (amount 0) return 0;sort(coins.rbegin(), coins.rend());int ans INT_MAX;coinChange(coins, amount, 0, 0, ans);return ans INT_MAX ? -1 : ans;
}
