01_爬楼梯

# 用时16ms
class Solution(object):
    def climbStairs(self, n):
        """
        :type n: int
        :rtype: int
        思路：最多能有几个2 比如 4 最多有2个2
        0个2的时候 1个2的时候 2个2的时候
        """
        max_2 = n // 2

        # 当台阶为1的情况
        if max_2 == 0:
            return 1

        count = 1
        for i in range(1, max_2 + 1):
            one_num = n - i * 2

            # 求 one_num个1 和 i个2 的 排列组合
            count = count + self.help(one_num + i) / \
                self.help(one_num) / self.help(i)
        return count

    def help(self, n):
        """
        求阶乘
        :param n:
        :return:
        """
        s = 1
        for i in range(1, n + 1):
            s *= i
        return s


# leetcode上最优解 用时0ms
class Solution2(object):
    def climbStairs(self, n):
        """
        :type n: int
        :rtype: int
        """
        f = []
        f.append(1)
        f.append(2)
        if n == 1:
            return 1
        if n == 2:
            return 2
        for i in range(2, n):
            f.append(f[i - 1] + f[i - 2])
        print(f)
        return f[-1]


# 1 2
# 1 2 3
# 1 2 3 5
#
# 1 2 3 5 8 这不是斐波那契吗

# 分类计数原理，也就是加法原理：如果完成一件事的方法分为（不重不漏的）两类，第一类有x种方法，第二类有y种方法，那么完成这件事的方法共有x+y种。
# 这个很好理解，谁都想得通。
# 到本题，假设走到第n层楼梯的方法数为f(n)。
# 走到第n层楼梯的方法可以分为两类：第一类，先走到第n-1层，然后走一级楼梯，这类方法有f(n-1)种；
# 第二类，先走到第n-2层，然后走两级楼梯，这类方法有f(n-2)种。
# 仔细想想，这两类方法覆盖了到达第n层楼梯的所有方法，且彼此没有重复，那么根据加法计数原理：f(n)=f(n-1)+f(n-2)
n = 5
s = Solution2()
s.climbStairs(n)