剑指offer 青蛙爬楼梯（简单3）

题目

一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。

代码

class Solution:
    def __init__(self):
        self.stack=[1]
    def jumpFloorII(self,number):
        for i in range(0,number-1):
            self.stack.append(sum(self.stack)+1)
        return self.stack[number-1]

思路

青蛙每次跳台阶，可以把最后一步的长度用来划分情况，最后一步可以是0步(一次走到n)、可以是1步，可以是2步，....，可以是n-1步，然后总的种数就是1+Jump(n-1)+Jump(n-2)+...+Jump(1),其中Jump(1)=1.
可以这是一个求和的过程，可以考虑用列表加和来算[1,1+1,1+2+1,1+2+4+1,....，前面几项求和再加1]