70.爬楼梯

Question

老师，好像可以不用 数组 保存。使用两个变量。
这样 时间O(n) 空间 O(1) 解决。

func climbStairs(n int) int {
    pre, cur := 1, 1
    for i := 2; i <= n; i++ {
        pre, cur = cur, pre
        cur = pre + cur
    }
    return cur
}

Answer 1

liuyubobobo 2020-05-14 10:01:01

没问题的，本质就是动态规划的空间优化。

在这个课程后续，我会以背包问题为例，讲解动态规划问题空间的优化，之后，可以再回头看一眼这个优化，可能理解更深入：）

继续加油！：）

• 提问者 慕数据1402393 #1

  好的 老师～