动态规划
以下为 LeetCode 动态规划 相关问题解法记录。
问题分析：动态规划，f[i]表示第i阶的方法数，f[i] = f[i - 1] + f[i - 2]，f[0] = 1。
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| class Solution {
func climbStairs(_ n: Int) -> Int {
var f: [Int] = []
f.append(1)
for i in 1...n {
var one = f[i - 1]
var two = 0
if (i - 2 < 0) {
two = 0
} else {
two = f[i - 2]
}
f.append(one + two)
}
return f[n]
}
}
|
启发：递推。
问题分析：动态规划，f[i]表示第i阶最小花费，f[i] = min(f[i - 1] + cost[i], f[i - 2] + cost[i])，f[0] = cost[0]。
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| class Solution {
func minCostClimbingStairs(_ cost: [Int]) -> Int {
var f: [Int] = []
f.append(cost[0])
for i in 1...(cost.count + 1) {
var one = f[i - 1]
var two = 0
var now = 0
if i - 2 < 0 {
two = 0
} else {
two = f[i - 2]
}
if i >= cost.count {
now = 0
} else {
now = cost[i]
}
f.append(min(one + now, two + now))
}
return min(f[cost.count], f[cost.count + 1])
}
}
|
启发：可以直接使用min()，max()函数。