70_climbing_stairs

70. 爬楼梯 简单

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

注意：给定 n 是一个正整数。

示例 1：

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

示例 2：

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

代码参考：

// 一维 DP 问题
package main

import "fmt"

func main() {
    fmt.Println(climbStairs1(3)) // 3
    fmt.Println(climbStairs2(4)) // 5
    fmt.Println(climbStairs3(5)) // 8
}

// 时间复杂度 O(2^N) // 严重超时
// 空间复杂度 O(1)
func climbStairs1(n int) int {
    if n <= 2 {
        return n
    }
    return climbStairs1(n-1) + climbStairs1(n-2) // 存在大量重复计算
}

// 借助数组保存中间结果，避免重复计算
// O(N)
// O(N)
func climbStairs2(n int) int {
    steps := make([]int, n+1)
    steps[1], steps[2] = 1, 2 // 边界

    for i := 3; i <= n; i++ {
        steps[i] = steps[i-2] + steps[i-1] // 状态转移
    }

    return steps[n] // 最优子结构
}

// 向后累计步数
// O(N)
// O(1)
func climbStairs3(n int) int {
    if n == 1 {
        return 1
    }

    i, j := 1, 2
    for n > 2 {
        i, j = j, i+j // bottom -> up
        n--
    }
    return j
}