经典动态规划:「换硬币」系列三道问题详解 |
您所在的位置:网站首页 › 面额和面值 › 经典动态规划:「换硬币」系列三道问题详解 |
换硬币(Coin Change)问题是一道经典的动态规划入门题,但是你可能不太知道,LeetCode 上的换硬币问题其实是一个系列,共三道题目: LeetCode 322. Coin Change(Medium) LeetCode 377. Combination Sum IV(Medium) LeetCode 518. Coin Change 2(Medium) 其中,377 题虽然不叫 Coin Change,但是本质上和换硬币问题是一样的。 这一系列是比较考验技巧的三道题目,难度层层递进。第一道题是大家都熟悉的动态规划入门题;第二道题变为求方案数,需要我们不重复不遗漏;第三道题更有难度,需要扩充为二维动态规划,才能准确求出方案数量。 没有做过这个系列三道题的同学,不妨跟着本文看看三道题目的解法,理解其中的思路和技巧。下面我们一道一道地进行分析。 (一) 第 322 题:求最小硬币数LeetCode 322. Coin Change(Medium) 给定不同面额的硬币 coins 和金额 amount,计算凑成总金额所需的最少的硬币个数。如果没有任何一种方案能组成该金额,返回 -1。每种硬币的数量是无限的。 示例: 输入: coins = [1, 2, 5], amount = 11 输出: 3 解释: 11 = 5 + 5 + 1这第一道题目大家应该都做过,网上的各种解析也很泛滥。这里我们还是套用动态规划的解题四步骤来求解。 第一步,定义子问题。 我们设硬币面值的集合为 。子问题 可以定义为:「凑出金额 的最小硬币数」。那么原问题就是求 。 第二步,写出子问题的递推关系。 求「凑出金额 的最小硬币数」,我们可以尝试不同的硬币。如果使用了金额为 的硬币,问题就变成了「凑出金额 的最小硬币数」。我们要从各种尝试中选择硬币数量最小的那个结果。 这样我们就可以写出子问题的递推关系: 当然,不要忘记子问题的 base case: 它的含义是,当 amount 为 0 时,不需要任何硬币就已经凑出了目标金额。 第三步,确定 DP 数组的计算顺序。 确定 DP 数组计算顺序的重点是看子问题的依赖关系。我们以 为例,即有 1 元、2 元、5 元的硬币。这样 依赖于 、、,全部在 的左边。也就是说,DP 数组中的每个元素只依赖其左边的元素。 ![]() 既然 DP 数组中的依赖关系都是向右指的,那么 DP 数组的计算顺序就是从左到右。 处理 DP 数组中的无效元素。 至此,我们离写出题解代码已经很接近了,但还要处理一个编程上的细节:DP 数组中的无效元素。 可能存在一些金额是硬币凑不出来的。例如只有 2 元、5 元的硬币时,就凑不出 1 元、3 元的金额。这样 、 就是无效元素,不能参与子问题的计算。 |
今日新闻 |
点击排行 |
|
推荐新闻 |
图片新闻 |
|
专题文章 |
CopyRight 2018-2019 实验室设备网 版权所有 win10的实时保护怎么永久关闭 |