/**
518.零钱兑换II
题目
给定不同面额的硬币和一个总金额。写出函数来计算可以凑成总金额的硬币组合数。假设每一种面额的硬币有无限个。
示例 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 位符号整数
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/coin-change-2
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
测试代码
print(change(5, [1, 2, 5]))
笔记
这道题看起来和 39.组合总和 是差不多的
但是用递归的方式是会超时的, 因为这道题不需要具体的解, 只需要知道有多少种组合就行了
所以用动态规划
难点就在于推导出动态规划的公式
假设现在只有面额 2 的硬币,即 coin = 2
首先创建一个数组 dp 记录每个金额对应的组合
总金额 amount = 0 的时候, 一定有且仅有 1 种组合, dp[0] = 1
总金额 amount < coin 的时候, 一定有且仅有 0 种组合, dp[1] = 0
总金额 amount = 2 的时候, 有 1 种组合, dp[2] = 1 = dp[2-2]
总金额 amount = 3 的时候, 有 0 种组合, dp[3] = 0 = dp[3-2]
总金额 amount = 4 的时候, 有 1 种组合, dp[4] = 1 = dp[4-2] = dp[2-2]
总金额 amount = 5 的时候, 有 0 种组合, dp[5] = 0 = dp[5-2] = dp[3-2]
为什么会这样呢?
因为就同一个 coin 而言, amount >= coin的时候, amount 的组合个数, 肯定是和 amount - coin 的个数是相等的
即 dp[amount] = dp[amount-coin]
多个 coin 的时候, dp[amount] = dp[amount] + dp[amount-coin] 即可
假设 amount = 3, coins = [1, 2], dp = [1, 0, 0, 0]
当 coin = 1 的时候,
dp[3] = dp[2] = dp[1] = dp[0] = 1
dp = [1, 1, 1, 1]
当 coin = 2 的时候,
dp[2] = 1 + dp[0] = 2
dp[3] = 1 + dp[1] = 2
dp = [1, 1, 2, 2]
代码地址
https://github.com/zmfflying/ZMathCode
*/
解题代码
import Foundation
func change(_ amount: Int, _ coins: [Int]) -> Int {
var dp: [Int] = [Int].init(repeating: 0, count: amount+1)
dp[0] = 1
for coin in coins {
if coin > amount {
continue
}
for i in coin...amount {
dp[i] += dp[i-coin]
}
}
return dp[amount]
}
//递归 超时的
func change1(_ amount: Int, _ coins: [Int]) -> Int {
if amount == 0 {
return 1
}
var res = 0
let count = coins.count
func help(cur: Int, index: Int) {
if cur > amount || index >= count {
return
}
for i in index..<count {
let num = coins[i]
let newNum = num + cur
if newNum < amount {
help(cur: newNum, index: i)
} else if newNum == amount {
res += 1
}
}
}
help(cur: 0, index: 0)
return res
}
/**
746.使用最小花费爬楼梯
题目
数组的每个下标作为一个阶梯，第 i 个阶梯对应着一个非负数的体力花费值 cost[i]（下标从 0 开始）。
每当你爬上一个阶梯你都要花费对应的体力值，一旦支付了相应的体力值，你就可以选择向上爬一个阶梯或者爬两个阶梯。
请你找出达到楼层顶部的最低花费。在开始时，你可以选择从下标为 0 或 1 的元素作为初始阶梯。
示例 1：
输入：cost = [10, 15, 20]
输出：15
解释：最低花费是从 cost[1] 开始，然后走两步即可到阶梯顶，一共花费 15 。
示例 2：
输入：cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1]
输出：6
解释：最低花费方式是从 cost[0] 开始，逐个经过那些 1 ，跳过 cost[3] ，一共花费 6 。
提示：
cost 的长度范围是 [2, 1000]。
cost[i] 将会是一个整型数据，范围为 [0, 999] 。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/min-cost-climbing-stairs
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
测试代码
print(minCostClimbingStairs([10, 15, 20]))
笔记
数组里每个元素都有两个选择: 选择当前元素 和 不选择当前元素
如果选择当前元素 i, 那么花费就有两种可能:
第一种是选择了 i-1 和 i
第二种是选择了 i-2 和 i
如果不选择当前元素 i, 那么花费肯定就是选择了 i-1 的结果
根据这个思路,创建两个数组,分别记录每个元素选择当前和不选择当前的最小花费
最后在取出两个数组最后一个元素求最小值即可
优化:
不选择当前元素的花费 noCur[i] = cur[i-1]
所以其实一个数组就行了
代码地址
https://github.com/zmfflying/ZMathCode
*/
解题代码
import Foundation
func minCostClimbingStairs(_ cost: [Int]) -> Int {
//选择自己的情况
var cur: [Int] = [Int].init(repeating: 0, count: cost.count)
cur[0] = cost[0]
cur[1] = min(cost[0] + cost[1], cost[1])
//不选择自己的情况
var noCur: [Int] = [Int].init(repeating: 0, count: cost.count)
noCur[1] = cost[0]
for i in 2..<cost.count {
//选择i的花费可能有两种:
//第一种是选择了 i-1 和 i
//第二种是选择了 i-2 和 i
cur[i] = min(cur[i-1] + cost[i], cur[i-2] + cost[i])
//不选择i的花费只可能有一种: 选择了 i-1
noCur[i] = cur[i-1]
}
return min(cur.last!, noCur.last!)
}
// MARK: - 优化
func minCostClimbingStairs1(_ cost: [Int]) -> Int {
var cur: [Int] = [Int].init(repeating: 0, count: cost.count)
cur[0] = cost[0]
cur[1] = min(cost[0] + cost[1], cost[1])
for i in 2..<cost.count {
cur[i] = min(cur[i-1] + cost[i], cur[i-2] + cost[i])
}
return min(cur.last!, cur[cost.count - 2])
}
网友评论