climbing stairs爬楼梯

Easy, Dynamic Programming

楼梯有n阶，一次可爬一阶或两阶。有多少种爬梯方式。

典型的DP问题，考虑最后两梯，只能有两种情况。爬到n阶的方式是（n-1)阶和（n-2)阶的方式的和。

class Solution(object):
    def climbStairs(self, n):
        """
        :type n: int
        :rtype: int
        """
        if n==0 or n==1:
            return 1
        pre2, pre = 1, 1
        for _ in range(2,n+1):
            ways = pre2 + pre
            pre2, pre = pre, ways
        return ways