问题

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

思路

首先考虑n等于0、1、2时的特殊情况，f(0) = 0 f(1) = 1 f(2) = 2
其次，当n=3时，青蛙的第一跳有两种情况：跳1级台阶或者跳两级台阶
假如跳一级，那么 剩下的两级台阶就是f(2)；假如跳两级，那么剩下的一级台阶就是f(1)，因此f(3)=f(2)+f(1)
当n = 4时，f(4) = f(3) +f(2)
以此类推………..可以联想到斐波拉契数列（Fibonacci数列）

方法一，递归

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
package main

import (
    "fmt"
    "time"
)

func main() {
	t1 := time.Now()
	a := jump(42);
	elapsed := time.Since(t1)//运行时间 

	t2 := time.Now()
	b := jump2(42);
	
	elapsed2 := time.Since(t2)
	fmt.Println(a);
	fmt.Println(elapsed);	// 2.0183411s

	fmt.Println(b);
	fmt.Println(elapsed2);	// 0s
}

/**
 * 递归
 */
func jump(n int) int {
	var tmp int
	if n == 1 || n ==2{
		tmp = n
	}else{
		tmp = jump(n-1) + jump(n-2)
	}
	return tmp
}

方法一，迭代

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/**
 * 迭代
 */
func jump2(n int) int {
	var tmp int
	if n == 1 || n ==2{
		tmp = n
	}

	a := 1
	b := 2
	for i:=3; i <= n; i++ {
		tmp = a + b
		a = b
		b = tmp
	}
	return tmp
}