用背包问题思路解决 322. Coin Change(完全背包)
首先需要明白 0-1 背包问题中的放置表格,见 “玩转算法面试 从真题到思维全面提升算法思维” 9-5 节,本题思路类似
表格纵向为:只考虑第 [0 …,… index] 种硬币(物品)
表格横向为:需要兑换的金额(背包容量)为 j
表格内容为:在横向和纵向的条件下,最少的硬币(物品)数
即:通过表格列举出,当硬币种类为 [0 …,… index] 种,兑换金额为 j 时,最少的硬币数量
以 Example 1 为例,可以画出下面的表格
Input: coins = [1, 2, 5], amount = 11
Output: 3
Explanation: 11 = 5 + 5 + 1
硬币&金额 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 |
---|---|---|---|---|---|---|---|---|---|---|---|---|
1 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 |
2 | 0 | 1 | 1 | 2 | 2 | 3 | 3 | 4 | 4 | 5 | 5 | 6 |
5 | 0 | 1 | 1 | 2 | 2 | 1 | 2 | 2 | 3 | 3 | 2 | 3 |
第一行:当只考虑面值为 1 的硬币时,兑换总金额为 0 1 2 3… 时,最少需要 0 1 2 3… 个
从第二行开始是关键,举例来说:
若想求只考虑面值为 1 和 2 的硬币时,兑换总金额为 7 最少有几种情况,即表格里加粗的数字是多少,可以这样考虑:
所求的问题可以拆分成这两种情况:
(1) 不使用面值为 2 的进行兑换,则问题变为 “只考虑面值为 1 的硬币时,兑换总金额为 7 最少有几种情况”,这个问题在第一行已经解决,就是上一格的元素,7
(2) 使用至少一个面值为 2 的进行兑换,首先拿一个 2,这样用了一个硬币,剩余金额为 7 - 2 = 5
子问题变为 “考虑面值为 1 和 2 的硬币,兑换总金额为 5” 最少有几种情况,注意子问题仍还需要 “考虑面值为 1 和 2”,而不是只考虑 1,因为可以使用多次 2!,这个子问题的解就是第二行纵坐标为 5 的格子元素的值,即为 3,加上之前用过的一个 “2”,所以需要 3 + 1 = 4 个。
同样,第三行拆分成 “不使用面值为 5 的进行兑换,即只考虑面值为 1 2” 和 “使用至少一个面值为 5 的进行兑换”
比如第 i 行第 j 列,第 i 行(从0开始)对应的面值是 coins[i],第一种情况为 table[i - 1][j],第二种情况为 table[i][j - coins[i]] + 1,取两者最小值即可。不过要注意如果其中一种情况兑换不了,那格子元素的值只能是能兑换的那种情况的值,如果两种情况都兑换不了,就记为 -1,这样双重循环填满这个表格,右下角的元素即为问题的解。
源自于:http://www.imooc.com/article/288317
最新文章
- webform 上传
- C#基础整理参数
- MYSQL基础知识总结
- Java并发编程核心方法与框架-Semaphore的使用
- shell中使用echo命令改变输出显示样式
- 2013 Multi-University Training Contest 2 Balls Rearrangement
- SpringNote01.基于SpringMVC-Hibernate的Blog系统
- 「OC」内存管理
- DDNS client on a Linux machine
- Python之路-python介绍
- 手机自动化测试:appium源码分析之bootstrap三
- Novate 网络库:Retrofit2.0和RxJava的又一次完美改进加强(Tamic博客 -CSDN)
- Android 网络优化,使用 HTTPDNS 优化 DNS,从原理到 OkHttp 集成
- vscode 前端插件推荐
- sqlserver日期函数大全
- ELK之安装了search guard认证后安装elasticsearch-head
- MVC,MVVM,MVP的区别/ Vue中忽略的知识点!
- 第三章 Typescript 基本数据类型
- std__vector介绍
- Magento 2中文文档教程 - Magento 2.1.x 系统需求