leetcode-70 爬楼梯
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
注意：给定 n 是一个正整数。
原问题可以等价转换为有多少种方法可以从第 1 个台阶爬到第 N 个台阶，这个问题可以拆成如下 N 个子问题
子问题 1: 多少种方法可以从第 1 个台阶爬到第 1 个台阶
子问题 2: 多少种方法可以从第 1 个台阶爬到第 2 个台阶
... ...
子问题 N-1: 多少种方法可以从第 1 个台阶爬到第 N-1 个台阶
很容易发现子问题为有多少种方法可以从第 1 个台阶爬到第 N-1 个台阶
暴力递归
将上述过程转换成递归过程
1、先求出有多少种方法可以从n-1爬一步到第N个台阶
2、然后求出有多少种方法可以从n-2爬两步到第N个台阶
然后问题1又有：
1、有多少种方法可以从n-2爬一步到第N-1个台阶
2、有多少种方法可以从n-2爬两步到第N-2个台阶
等等。。
func palouDuigui(_ n: Int) -> Int{
if n == 1 {
return 1
}else if n == 2 {
return 2
}else{
return palouDuigui(n - 1) + palouDuigui(n - 2)
}
}
给暴力递归优化-加缓存
求解过程中会有很多重复计算，为减少计算量，可以添加缓存
//计算爬楼方式
func climbStairs(_ n: Int) -> Int {
var arr = [Int](repeating: -1 , count: n )
return palou(n,arr: &arr)
}
//爬楼递归方法
func palou(_ n: Int, arr:inout [Int]) -> Int {
if arr[n - 1] != -1 {
return arr[n - 1]
}
var ans:Int = -1
if n == 1 {
ans = 1
}else if n == 2 {
ans = 2
}else{
ans = palou(n - 1,arr: &arr) + palou(n - 2,arr:&arr)
}
arr[n - 1] = ans
return ans
}
从暴力递归到动态优化
分析：
从构建二维数组的过程中不难发现每次都是取的数组的前一个数据以及数组的前前一个数据，所以：完全可以用一个for循环实现：
func climbStairs(_ n: Int) -> Int {
if n < 3 {
return n
}
var arr = [Int](repeating: -1 , count: n )
arr[0] = 1
arr[1] = 2
for i in 2..<n {
arr[i] = arr[i - 1] + arr[i - 2]
}
return arr[n - 1]
}
在此过程中又会发现arr数组在用过一次之后就没有用了，即：
dp[N] 的状态永远依赖于 dp[N-1] 和 dp[N-2]，我们可以使用滚动数组的思想来把 dp 数组优化掉。滚动数组思想表示在一个数组中(不限维度)，某一个下标为 N 的元素总是依赖于这个数组前面的某些元素，当求出这个下标为 N 的元素后，前面的某些元素就可以丢弃不要了，这时就可以优化数组空间，减少内存的使用。
func climbStairsEnd(_ n: Int) -> Int {
if n < 3 {
return n
}
var arr = [Int](repeating: -1 , count: 2 )
arr[0] = 1
arr[1] = 2
for _ in 2..<n {
let nextNum = arr[0] + arr[1]
arr[0] = arr[1]
arr[1] = nextNum
}
return arr[1]
}
