70.E 爬楼梯

Problem: 70. 爬楼梯

思路

动态规划。

考虑到最后一步可以是跨了一级或者两级台阶，可以得到：

f(n) = f(n-1) + f(n-2)

Code

递归代码：会超时

func climbStairs(n int) int {
	if n <= 2 {
		return n
	}

	return climbStairs(n-1) + climbStairs(n-2)
}

优化后代码：

func climbStairs(n int) int {
	if n <= 2 {
		return n
	}

	n1 := 1
	n2 := 2
	for i := 3; i <= n; i++ {
		n3 := n1 + n2
		n1 = n2
		n2 = n3
	}

	return n2
}