题目地址(518. 零钱兑换 II)
https://leetcode-cn.com/problems/coin-change-2/description/
题目描述
给定不同面额的硬币和一个总金额。写出函数来计算可以凑成总金额的硬币组合数。假设每一种面额的硬币有无限个。
示例 1:
输入: amount = 5, coins = [1, 2, 5]
输出: 4
解释: 有四种方式可以凑成总金额:
5=5
5=2+2+1
5=2+1+1+1
5=1+1+1+1+1
示例 2:
输入: amount = 3, coins = [2]
输出: 0
解释: 只用面额 2 的硬币不能凑成总金额 3。
示例 3:
输入: amount = 10, coins = [10]
输出: 1
注意:
你可以假设:
0 <= amount (总金额) <= 5000
1 <= coin (硬币面额) <= 5000
硬币种类不超过 500 种
结果符合 32 位符号整数
思路
这个题目和 coin-change 的思路比较类似。
我们还是按照 coin-change 的思路来, 如果将问题画出来大概是这样:
进一步我们可以对问题进行空间复杂度上的优化(这种写法比较难以理解,但是相对更省空间)
这里用动图会更好理解, 有时间的话我会做一个动图出来, 现在大家脑补一下吧
关键点解析
-
动态规划
-
子问题
用 dp[i] 来表示组成 i 块钱,需要最少的硬币数,那么
-
第 j 个硬币我可以选择不拿 这个时候, 组成数 = dp[i]
-
第 j 个硬币我可以选择拿 这个时候, 组成数 = dp[i - coins[j]] + dp[i]
-
和背包问题不同, 硬币是可以拿任意个
-
对于每一个 dp[i] 我们都选择遍历一遍 coin, 不断更新 dp[i]
eg:
if (amount === 0) return 1; const dp = [Array(amount + 1).fill(1)]; for (let i = 1; i < amount + 1; i++) { dp[i] = Array(coins.length + 1).fill(0); for (let j = 1; j < coins.length + 1; j++) { // 从1开始可以简化运算 if (i - coins[j - 1] >= 0) { // 注意这里是coins[j -1]而不是coins[j] dp[i][j] = dp[i][j - 1] + dp[i - coins[j - 1]][j]; // 由于可以重复使用硬币所以这里是j不是j-1 } else { dp[i][j] = dp[i][j - 1]; } } } return dp[dp.length - 1][coins.length];
- 当我们选择一维数组去解的时候,内外循环将会对结果造成影响
eg:
// 这种答案是不对的。 // 原因在于比如amount = 5, coins = [1,2,5] // 这种算法会将[1,2,2] [2,1,2] [2, 2, 1] 算成不同的 if (amount === 0) return 1; const dp = [1].concat(Array(amount).fill(0)); for (let i = 1; i < amount + 1; i++) { for (let j = 0; j < coins.length; j++) { if (i - coins[j] >= 0) { dp[i] = dp[i] + dp[i - coins[j]]; } } } return dp[dp.length - 1]; // 正确的写法应该是内外循环调换一下, 具体可以看下方代码区
代码
/* * @lc app=leetcode id=518 lang=javascript * * [518] Coin Change 2 * */ /** * @param {number} amount * @param {number[]} coins * @return {number} */ var change = function(amount, coins) { if (amount === 0) return 1; const dp = [1].concat(Array(amount).fill(0)); for (let j = 0; j < coins.length; j++) { for (let i = 1; i < amount + 1; i++) { if (i - coins[j] >= 0) { dp[i] = dp[i] + dp[i - coins[j]]; } } } return dp[dp.length - 1]; };
扩展
这是一道很简单描述的题目, 因此很多时候会被用到大公司的电面中。
相似问题:
322.coin-change
LeetCode题解322.coin-change题目地址 https://leetcode.com/problems/coin-change/description/ 题目描述 You are given coins of different denominations and a total amount of money amount. Write a function to compute the …
LeetCode题解计算机为什么是基于二进制的?可以是三进制么?二进制有什么好处?题解:为什么叫电子计算机?算盘应该没有二进制
LeetCode题解深度优先遍历和回溯的关系?深度优先遍历的范围更大还是回溯的范围更大?为什么?题解:我的理解是:dfs是回溯思想的一种体现- 回溯:是在整个搜索空间中搜索出可行解,在搜索过程中不断剪枝回退,这是回溯的思想,这个搜索空间并没有限制于特定的数据结构。- dfs:dfs是指特定的数据结构中如图,树(特殊的图)中搜索答案,范围限制在了特定的数据结构。个人拙见。
LeetCode题解盲人买袜子。他们都各自买了两对黑袜和两对白袜,八对袜子的布质、大小完全相同,而每对袜子都有一张商标纸连着。两位盲人不小心将八对袜子混在一起。他们每人怎样才能取回黑袜和白袜各两对呢?题解:暴力破解, 把袜子都拆开 一人一只 哈哈
LeetCode题解白石搭白塔输入黑块和白块的数量,用输入的方块数目建塔,输出最大高度和种数,两种方法至少一层颜色不同才能算不同的方法塔满足下列要求:1. 塔底层块数和高度数值相同,逐层递减1,最高层为12. 每层颜色相同