70. 爬楼梯

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

  1. //动态规划法，就是递归，有个记忆化搜索dp，自顶而下
  2. func climbStairs(n int) int {
  3.     if n <= 1 {
  4.         return n
  5.     }
  7.     dp := make([]int, n+1)
  8.     dp[0], dp[1] = 1, 1
  10.     for i :=2; i <= n; i++ {
  11.         dp[i] = dp[i-1] + dp[i-2]
  12.     }
  13.     return dp[n]
  14. }
//动态规划 优化空间复杂度On->O1，自底向上
func climbStairs(n int) int {
    if n <= 1 {
        return n
    }

    temp := 0
    prev, cur := 1, 1

    for i := 2; i <= n; i++ {
        temp = cur + prev        //最优子结构，前两项和，这个技巧就是所谓的「状态压缩」
        prev = cur
        cur = temp
    }
    return cur
}