入门easy题

70. Climbing Stairs

Difficulty: Easy

You are climbing a stair case. It takes n steps to reach to the top.

Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

Hide Company Tags Adobe Apple

思路：状态：dp[i]表示当有i步时有几种走法。 初始状态：dp[1]=1当n=1是，只有一种方法，一步上去；dp【2】=2当n=2时，要么一次一步上去，要么一次2步一次0步上去，共有两种方法。状态转移方程：dp[i] = dp[i-1]+dp[i-2]。这是一种bottom up的dp时间，属于iteration的方法。

class Solution(object):
    def climbStairs(self, n):
        """
        :type n: int
        :rtype: int
        """
        if n < 3:
            return n
        dp = [0]*(n+1)
        dp[1], dp[2] = 1, 2
        for i in range(3, n+1):
            dp[i] = dp[i-1] + dp[i-2]
        return dp[n]