69.md

跳台阶

就是个斐波那契数列

题目

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

思路

• 假设对于第 n 级台阶，总共有 f(n) 种跳法.
• 那么 f(n) = f(n-1) + f(n-2)，其中 f(1) = 1, f(2) = 2
• 其中肯定有重复运算的，搞个 map 备忘录存着

复杂度

• 如果单纯递归时间复杂度是 O(2^n)
• 加上记忆化搜索后时间复杂度是 O(n)，因为没有了重复计算
• 动态规划可以将空间复杂度降到 O(n) 甚至 O(1)

实现

package main

import (
	"fmt"
)

func main() {
	fmt.Println(jumpFloor1(5))
	fmt.Println(jumpFloor2(5))
	fmt.Println(jumpFloor3(5))
	fmt.Println(jumpFloor4(5))
}

// 纯递归
func jumpFloor1(number int) int {
	if number <= 1 {
		return 1
	}
	return jumpFloor1(number-1) + jumpFloor1(number-2)
}

// 备忘录
func jumpFloor2(number int) int {
	note := make([]int, number)
	return fib(number, note)
}

func fib(number int, note []int) int {
	if number <= 1 {
		return 1
	}

	if note[number-1] != 0 {
		return note[number-1]
	}

	res := fib(number-1, note) + fib(number-2, note)
	note[number-1] = res
	return res
}

// 备忘录升级为动态规划, 不用递归的过程, 直接从子树求得答案, 过程是从下往上
func jumpFloor3(number int) int {
	if number <= 1 {
		return 1
	}
	note := make([]int, number)
	note[0] = 1
	note[1] = 2
	for i := 2; i < number; i++ {
		note[i] = note[i-1] + note[i-2]
	}
	return note[number-1]
}

// 究极动态规划
func jumpFloor4(number int) int {
	if number <= 1 {
		return 1
	}
	var a = 1
	var b = 1
	var c int
	for i := 2; i <= number; i++ {
		c = a + b
		a = b
		b = c
	}
	return c
}