剑指offer 跳台阶

Posted on |

题目描述

一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法（先后次序不同算不同的结果）。

方法

最简单的情况
如果只有一级台阶，只有一种跳法。
如果有两级台阶，有两种跳法：一种分两次跳，每次跳1级；一种一次跳2级。

一般情况
把n级台阶时的跳法看作n的函数，记作f(n)
当n>=2时，第一次跳的时候就有两种选择：

  • 一是第一次只跳1级，此时跳法数目等于后面剩下的n-1级台阶的跳法数目f(n-1)；
  • 二是第一次跳2级，此时跳法数目等于后面剩下的n-2级台阶的跳法数目f(n-2)
    因此，n阶台阶的跳法数目f(n)=f(n-1)+f(n-2)
    这就是斐波那契数列
1
2
3
4
5
6
7
8
9
10
11
12
13
# -*- coding:utf-8 -*-
class Solution:
    def jumpFloor(self, number):
        # write code here
        if number==1:
            return 1

        dp=[0]*number
        dp[0],dp[1]=1,2

        for i in range(2,number):
            dp[i]=dp[i-1]+dp[i-2]
        return dp[-1]