算法动态规划

爬楼梯

文章目录
  1. 1. 问题描述
  2. 2. 分析

爬楼梯

问题描述

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
注意：给定 n 是一个正整数。
示例 1：
输入： 2
输出： 2
解释： 有两种方法可以爬到楼顶。
1.  1 阶 + 1 阶
2.  2 阶

示例 2：
输入： 3
输出： 3
解释： 有三种方法可以爬到楼顶。
1.  1 阶 + 1 阶 + 1 阶
2.  1 阶 + 2 阶
3.  2 阶 + 1 阶

分析

  1. 可以查分为子问题，division 使用递归暴力解决问题
    1. 找到递归关系
    2. 递归终止条件
  2. 优化使用记忆化递归
  3. 动态规划

假设只有 5 个台阶

根据图总共有 8 个方式走到第 5 个台阶

可以得到递归关系
climbStairs(i,n) = climbStairs(i+1,n) + climbStairs(i+2,n)

参数:
i: 当前第几层台阶
n: 总台阶数，为了提供终止递归条件

1
2
3
4
5
6
7
8
9
10
11
12
func climbStairs(_ n: Int) -> Int {
  func climbStairs_(_ i: Int, _ n: Int) -> Int {
    if i > n {
      return 0
    }else if i == n {
      return 1
    }else {
      return climbStairs_(i+1, n) + climbStairs_(i+2, n)
    }
  }
  return climbStairs_(0, n)
}

从上图可以看出有很多重复的节点，每个节点都是一次 climbStairs(i,n) 调用所以可以给递归添加缓存

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
func climbStairs(_ n: Int) -> Int {
  var memo: [Int?] = Array(repeating: nil, count: n)
  
  func climbStairs(_ n: Int, _ memo: inout [Int?]) -> Int {
    if n <= 2 {
      return n
    }
    let index = n - 1
    if memo[index] != nil {
      return memo[index]!
    }else {
      memo[index] = climbStairs(n - 1, &memo) + climbStairs(n - 2, &memo)
    }
    return memo[index]!
  }
  
  let res = climbStairs(n, &memo)
  return res
}

以上都是自顶向下的逐一拆分子问题
分冶算法dp表存储路径

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
func climbStairs(_ n: Int) -> Int {
  guard n > 1 else { return n }
  
  var dp: [Int] = [0,1,2]
  var i = 3
  while i <= n {
    dp.append(dp[i-1] + dp[i - 2])
    i += 1
  }
  return dp[n]
}

斐波那契数列

func climbStairs(_ n: Int) -> Int {
  guard n > 1 else { return n }
  
  var first = 1
  var second = 2
  var i = 3
  while i <= n {
    let third = first + second
    first = second
    second = third
    i += 1
  }
  return second
}