4

经典面试题：青蛙

 2 years ago
source link: https://zkqiang.cn/posts/14690cf1/
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.

「剑指Offer」里的经典题目，近期群里聊到这题，特来复习一波。

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

首先跳到 n 级台阶可以分解为两种情况：

  1. 之前跳到 n-1 级台阶，然后再跳 1 级到达 n 级；
  2. 之前跳到 n-2 级台阶，然后再跳 2 级到达 n 级；

因此 n 级跳法数量，等于这两种情况之和。
即 F(n) = F(n-1) + F(n-2)

同理可继续推导：
F(n-1) = F(n-2) + F(n-3)
F(n-2) = F(n-3) + F(n-4)
…
F(2) = F(1) + F(0)
F(1) = 1
F(0) = 1

可见这是斐波那契数列，数列中从第三个数开始，每个数都是前两个数之和。那么只需从 F(0) + F(1) = F(2) 开始计算，一直加到 F(n) 即可得出结果。

Golang 版

func JumpFloor(n int) int {
    a, b := 1, 1
    for ; n > 0; n-- {  
        a, b = b, a + b
    }  
    return a
}

Python 版

def jump_floor(n):
    a, b = 1, 1
    for _ in range(n):
        a, b = b, a + b
    return a

report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK