033-力扣刷题-70--爬楼梯

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

注意：给定 n 是一个正整数。

示例 1：

1
2
3
4
5
输入： 2
输出： 2
解释： 有两种方法可以爬到楼顶。
1.  1 阶 + 1 阶
2.  2 阶

示例 2：

1
2
3
4
5
6
输入： 3
输出： 3
解释： 有三种方法可以爬到楼顶。
1.  1 阶 + 1 阶 + 1 阶
2.  1 阶 + 2 阶
3.  2 阶 + 1 阶

image.png

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
class Solution(object):
    def climbStairs(self, n):
        """
        :type n: int
        :rtype: int
        """
        a,b=0,1  #实际上就是个斐波那契数列,只不过a从0,b从1开始,原因是我们要循环的是n次,所以第一次循环得到的是1,1继续向下循环就好了
        for i in range(n):
            a,b=b,a+b
        return b#返回最后b就是组合的种数

分类计数原理，也就是加法原理：如果完成一件事的方法分为（不重不漏的）两类，第一类有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)。