70. 爬楼梯

[yankewei]

假设你正在爬楼梯。需要 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 阶

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/climbing-stairs

解答

暴力解法（超时）

每次爬楼梯的时候有两种选择，把这两种选择相加即可

func climbStairs(n int) int {
    return deep(0, n)
}

func deep(i, n int) int {
    // 下边两个判断是一个基本case，列出来即可
    if i > n {
        return 0
    }
    if i == n {
        return 1
    }
    return deep(i+1, n) + deep(i+2, n)
}

递归 + 字典

上述暴力法其实可以优化的，因为过程中我们会计算多次相同的deep(i， n)，那么我们就可以在计算完之后进行保存，如果下次用到了可以直接调用

func climbStairs(n int) int {
    m := make(map[int]int, n)
    return deep(0, n, m)
}

func deep(i, n int, m map[int]int) int {
    if i > n {
	return 0
    }
    if i == n {
	return 1
    }
    if v, e := m[i]; e {
	return v
    }
    m[i] = deep(i+1, n, m) + deep(i+2, n, m)
    return m[i]
}

动态规划

其实，到达m层的方法，就是到达m-1层的方法加上到达m-2层的方法，为什么呢，因为题目给出了一次可以爬一个台阶或者两个台阶，也就是到达m层的方法，要不是爬了一个台阶，要不就是爬了两个台阶。所以等于m-1 + m-2种不同的方法。

func climbStairs(n int) int {
    dp := make(map[int]int, n)
    dp[1] = 1
    dp[2] = 2
    for i := 3; i <= n; i++ {
	dp[i] = dp[i-2] + dp[i-1]
    }
    return dp[n]
}

上述代码还有空间优化的可能，因为dp这个map有n个元素，其实我们每次都只是用了两个.

func climbStairs(n int) int {
    dp := [2]int{1, 2}
    if n < 3 {
        return dp[n-1]
    }
    for i := 3; i <= n; i++ {
	tmp := dp[1]
	dp[1] = dp[0] + tmp
	dp[0] = tmp
    }
    return dp[1]
}