我是靠谱客的博主 风趣康乃馨,这篇文章主要介绍【剑指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

最后

以上就是风趣康乃馨最近收集整理的关于【剑指Offer】 9.变态跳台阶 python实现的全部内容,更多相关【剑指Offer】内容请搜索靠谱客的其他文章。

本图文内容来源于网友提供,作为学习参考使用,或来自网络收集整理,版权属于原作者所有。
点赞(44)

评论列表共有 0 条评论

立即
投稿
返回
顶部