golang-面试题-跳台阶问题（斐波那契）

问题：

如果一只青蛙实现每次只可以跳一次或者两次台阶，那么他跳到n级台阶有多少中可能
​

数学推导：

• 假设他跳n级台阶有f(n)种可能，现在我们要想办法求出来f（n）
• 从终点n级，往后推导，那么他跳到第n级台阶的最后一跳只有两种可能
  • 从n-1级台阶，跳一下到第n级
  • 从n-2级台阶，跳两下到第n级
• 那也就是说跳到f(n)的可能性 = f(n-1) + f(n-2) # 满足斐波那契数列啦
• 那我们其实只要知道f(1) 和 f（2）是多少，我们就可以推导出后面的f（n）了

golang代码实现 – 简单版

• 时间复杂度：O（N^2）

package main

import "fmt"

func fib(n int)  int{
	if n < 1 {
		return 0
	}
	if n == 1 || n == 2{
		return n
	}

	return fib(n -1 ) + fib(n -2)
}

func main() {
	a := fib(7)
	fmt.Println(a)

}

复制代码

golang代码实现-缓存版

• 时间复杂度 O(n)

package main

import "fmt"

func helper(memo map[int]int, n int) int {
	if n == 1 || n == 2 {
		return n
	}
	if count,ok := memo[n];ok{
		return count
	}
	memo[n] = helper(memo,n-1) + helper(memo, n -2)
	return memo[n]

}

func fib(n int) int {
	if n < 1 {
		return 0
	}

	memo := make(map[int]int)
	return helper(memo, n)
}

func main() {
	a := fib(7)
	fmt.Println(a)

}
复制代码

​

golang代码实现 – 动态规划(从底向上)

• 时间复杂度 O（N）

package main

import "fmt"

func dpFib(n int) int {
	if n < 1 {
		return 0
	}
	if n == 1 || n == 2 {
		return n
	}

	//
	dpTable := make([]int, n+1)

	// base case
	dpTable[1] = 1
	dpTable[2] = 2

	// 状态转移
	for i := 3; i <= n; i++ {
		dpTable[i] = dpTable[i-1] + dpTable[i-2]
	}
	return dpTable[n]

}

func main() {
	a := dpFib(7)
	fmt.Println(a)

}

复制代码

golang代码实现-动态规划（状态压缩版本）

• 时间复杂度 O（N）
• 空间复杂度O（1）对比以上用了数组辅助的是O（N）

package main

import "fmt"

func dpFibCompress(n int) int {
	if n < 1 {
		return 0
	}
	if n == 1 || n == 2 {
		return n
	}

	one := 1
	two := 2
	var result int
	
	for i := 3; i <= n; i++ {
		// 省了维护数组的开销
		result = one + two
		one = two
		two = result
	}
	return result

}

func main() {
	a := dpFibCompress(7)
	fmt.Println(a)

}

复制代码