70 爬楼梯

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


if __name__ == '__main__':
    testcase = 3
    print(Solution().climbStairs(testcase))

本题的思想是基于动态规划

在第 i i i级台阶时，可以从第 i − 1 i-1 i−1级跳一步而来，也可以从第 i − 2 i-2 i−2​​级跳两步而来

设 d p [ i ] dp[i] dp[i]是第 i i i级台阶的总情况数，则有 d p [ i ] = d p [ i − 1 ] + d p [ i − 2 ] dp[i]=dp[i-1]+dp[i-2] dp[i]=dp[i−1]+dp[i−2]

注意初始化条件 d p [ 0 ] = 1 , d p [ 1 ] = 2 dp[0]=1,dp[1]=2 dp[0]=1,dp[1]=2