题解 | #跳台阶扩展问题#

递归法和动态规划法解决本题
（1）递归法
这是一种自上而下的解决方法，即要想求f(n)，需要先求f(n-1)，f(n-2),f(n-3)...，依次类推。这种方法的实现是通过调用函数本身来实现的。
实现代码如下：
class Solution:

def jumpFloorII(self, number):
    # write code here
    #递归
    if number==0:
        return 1
    f_num=0
    for i in range(1,number+1):
        f_num+=self.jumpFloorII(number-i)
    return f_num

(2)动态规划法
这是一种自下而上的解决办法，即要想求f(n)，先通过f(0),f(1)求f(2),再求f(3)...,以此类推，知道求到f(n)。这种方法的实现一般是通过for循环来实现。(动态规划法计算量要小，因为没有重复计算)
实现代码如下：
class Solution:

def jumpFloorII(self,number):
    process=[0]*(number+1)
    process[0]=1
    process[1]=1
    for i in range(2,number+1):
        a=0
        for j in range(i):
            a+=process[j]
        process[i]=a
    return process[number]