129-70. 爬楼梯

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？(老规矩前两个哥写的,后面抄的,而且我写的也是我看了别人解释之后才发现这是个斐波那契数列问题)
class Solution(object):
    def climbStairs1(self, n):
        """
        :type n: int
        :rtype: int
        """
        if n <= 2:
            return n

        dp = [-1 for i in range(n+1)]
        dp[1] = 1
        dp[2] = 2

        for i in range(3, n+1):
            dp[i] = dp[i-1] + dp[i-2]
        return dp[n]

    def climbStairs2(self, n):
        """
        :type n: int
        :rtype: int
        """
        if n <= 2:
            return n

        dp = [-1 for i in range(n+1)]
        dp[1] = 1
        dp[2] = 2

        def inner(n, dp):
            if dp[n] != -1:
                return dp[n]
            dp[n] = inner(n-1, dp) + inner(n-2, dp)
            return dp[n]
        return inner(n, dp)

    def climbStairs3(self, n):
        """
        :type n: int
        :rtype: int
        """
        dp = [-1] * 2
        dp[0] = 2
        dp[1] = 1

        for i in range(3, n+1):
            dp[i & 1] = dp[(i-1) & 1] + dp[(i-2) & 1]
        return dp[n & 1]

    def climbStairs4(self, n):
        """
        这个方式应该是一个定理
        :type n: int
        :rtype: int
        """
        kinds = 0

        for num2 in range(int((n - n % 2) / 2 + 1)):
            kinds = kinds + self.jiecheng(n - num2) / self.jiecheng(n - 2 * num2) / self.jiecheng(num2)
        return kinds

    def jiecheng(self, num):
        ret = 1
        if num == 0:
            return 1
        for i in range(1, num + 1):
            ret = ret * i
        return ret

    def climbStairs(self, n):
        """
        :type n: int
        :rtype: int
        """
        if n < 3:
            return n

        a = 1
        b = 2
        c = 0
        for i in range(3, n + 1):
            c = a + b
            a, b = b, c
        return c


if __name__ == '__main__':
    s1 = Solution()
    print(s1.climbStairs(9))