《苦练算法》

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

题目分析
如果是1级台阶故还是只有一种 f（1） = 1
因为n级台阶，第一步有n种跳法：跳1级、跳2级、。。。。跳n级
跳1级，剩下n-1级，则剩下跳法是f(n-1)
跳2级，剩下n-2级，则剩下跳法是f(n-2)
所以得出f(n)=f(n-1)+f(n-2)+…+f(1)
n-1时得出f(n-1)=f(n-2)+f(n-3)+…+f(1)

两个式子做一下化解得出f(n)=2*f(n-1)
所以实则还是递归，但是这里依然还是用迭代来做

代码如下

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

《苦练算法》

近期文章

近期评论

标签

热门

文章归档

分类目录

功能