【剑指Offer】 9.变态跳台阶 python实现

65 阅读 0 评论 43 点赞

我是靠谱客的博主风趣康乃馨，这篇文章主要介绍【剑指Offer】 9.变态跳台阶 python实现，现在分享给大家，希望可以做个参考。

题目描述

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

分析：找规律

输入	可能的跳法
f(1)	1
f(2)=2	(1,1)，(2)
f(3)=4	(1,1,1)，(1,2)，(2,1)，(3)
f(4)=8	(1,1,1,1)，(1,1,2)，(1,2,1)，(1,3)，(2,1,1)，(2,2)，(3,1)，(4)
f(5)	(1,1,1,1,1)，()，()

a[n]=a[n-1]+a[n-2]+…+a[1];…①
a[n-1]= a[n-2]+…+a[1];…②
两式相减可知：a[n]=2*a[n-1];

直接看图就知道：
在这里插入图片描述

非递归实现

# -*- coding:utf-8 -*-
class Solution:
    def jumpFloorII(self, number):
        # write code here
        if number == 1:
            return 1
        res = 2
        for i in range(2, number):
            res = res * 2
        return res