leetcode-70 爬楼梯

留言

简单的 DP，经典的爬楼梯问题。一个楼梯可以由 n-1 和 n-2 的楼梯爬上来。

这一题求解的值就是斐波那契数列。

70. 爬楼梯

和 剑指 Offer 10- II. 青蛙跳台阶问题相同

难度: 简单




动态规划解法:

1
2
3
4
5
6
7
8
func climbStairs(n int) int {
	dp := make([]int, n+1)
	dp[0], dp[1] = 1, 1
	for i := 2; i <= n; i++ {
		dp[i] = dp[i-1] + dp[i-2]
	}
	return dp[n]
}

https://www.google.com/search?q=%E8%B7%B3%E5%8F%B0%E9%98%B6+%E5%8A%A8%E6%80%81%E8%A7%84%E5%88%92&oq=%E8%B7%B3%E5%8F%B0%E9%98%B6&aqs=chrome.1.69i57j0i512l2j0i30l3j0i15i30j0i5i30.5151j0j1&sourceid=chrome&ie=UTF-8&bshm=bshwcqp/1


递归解法:


https://blog.csdn.net/fisherming/article/details/79828851

1
2
3
4
5
6
7
8
9
10
func climbStairs(n int) int {
	if n == 1 {
        return 1
    }

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

但用这种方式性能比较差~