剑指offer变态跳台阶python

题目描述

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

 

思路

和上一题类似的思路，第n级可以从n-1级跳1步，或者n-2级跳2步，或者n-3级跳3步.......所以，第n级台阶的跳法就是第n-1级的跳法+第n-2级的跳法+......第1级的tiaofa 。

设第n级台阶的跳法为F(n),则有

F(n) = F(n-1) + F(n-2) + F(n-3) + ...... + F(2) + F(1)

F(n-1) = F(n-2) + F(n-3) + ...... + F(2) + F(1)

所以

F(n) = F(n-1) + F(n-1) = 2F(n-1)

于是我们可以从定义一个list，依次类推出结果

代码

# -*- coding:utf-8 -*-
class Solution:
    def jumpFloorII(self, number):
        # write code here
        ans = [1,1]
        while number >= len(ans):
            ans.append(ans[-1]*2)
        return ans[number]