letcode[070] 爬楼梯

思路1：自拟思路——排列组合的思路（letcode没通过，但可行的方案）

转化题意，就是n能够被分成1和2的组合数有多少，例如7可以分解成以下4种类型：
[1,1,1,1,1,1,1]
[1,1,1,1,1,2]
[1,1,1,2,2]
[1,2,2,2]

结果的数量就是针对上面4种类型，每一种的步数组合，组合有：

每种组合的加总

我们知道组合公式如下：

组合公式

所以，我们先定义一个函数做x的排列递归，然后再循环加出结果。

总结： 大概是最笨的方法了。
用时： ms

class Solution:
    # 定义阶乘函数
    def fact(x):
        if x<2:
            return 1
        else:
            return x*fact(x-1)
        
    def climbStairs(n):
        m=n//2
        result=0
        for i in range(m+1):
            result+=(fact(n-i)/fact(i)/fact(n-2*i))
        return int(result)

思路2：网友思路——再想透一点，这其实就是斐波那契数列啊！

数学公式直接看图，所以直接递归：
总结： letcode超时，通不过；当然还有使用scipy和itemtool的组合工具就算的，letcode不支持import也就不能用
用时： ms

def climbStairs2(n):
    if n == 1:
        return 1
    elif n == 2:
        return 2
    else:
        return self.climbStairs(n - 1) + self.climbStairs(n - 2)

思路3：网友思路——其实递归不能用，用循环也是可以的

总结： (这个可以刷题通过）
用时：40 ms

def climbStairs3(n):
    if n==1:
        return 1
    if n==2:
        return 2
    else:
        values=[1,2]
        for i in range(2,n):
            values.append(values[i-1]+values[i-2])
        return values[-1]