70爬楼梯解题记录

最初想的是终于知道拆解重复的步骤，从而递归计算了，但是超时了

func climbStairs(n int) int {if n == 1 {return 1}if n == 2 {return 2}return climbStairs(n-1) + climbStairs(n-2)
}

这个让我想到了斐波那契的计算，也是因为没有保存已经计算过的值而超时了。

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