70. Climbing Stairs

一次能爬一个或两个台阶，有多少种方式爬到山顶

思路：动态规划，这个其实是斐波那契数列， dp[x] = dp[x-1] + dp[x-2]

1
2
3
4
5
6
7
8
9
10
11
class Solution:
    def climbStairs(self, n):
        """
        :type n: int
        :rtype: int
        """
        # 5 star 动态规划 dp[x] = dp[x-1] + dp[x-2]
        a, b = 1, 2
        for _ in range(n-1):
            a, b = b, a+b
        return a

Go:

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