第 N 个泰波那契数

泰波那契序列 Tn 定义如下： 

T0 = 0, T1 = 1, T2 = 1, 且在 n >= 0 的条件下 Tn+3 = Tn + Tn+1 + Tn+2

给你整数 n，请返回第 n 个泰波那契数 Tn 的值。

例子
输入：n = 4
输出：4
解释：
T_3 = 0 + 1 + 1 = 2
T_4 = 1 + 1 + 2 = 4

  • 分析

最先想到公式为Tn = T(n-3) + T(n-2) + T(n-1)

最简单的就是递归

1
2
3
4
5
6
7
8
9
10
11
12
13
func tribonacci(n int) int {
	var tn int
	if n == 0 {
		return 0
	}else if n == 1 {
		return 1
	}else if n == 2 {
		return 1
	}else {
		tn = tribonacci(n-3) + tribonacci(n-2) + tribonacci(n-1)
	}
	return tn
}

提交以后发现超时，超时的原因递归计算了很多重复性的工作，所以需要更加简单的方式

递推

递推其实我们只要存储最近三个数就可以计算出下一个数了

1
2
3
4
5
6
7
func tribonacci1(n int) int {
	a, b , c := 0,1,1
	for i := 0; i < n; i++ {
		a, b, c = b, c, a+b+c
	}
	return a
}

缓存+动态规划

这种方式就是用一个数组去缓存第n个位置的具体值是啥，然后需要的时候直接取出来，和递推方式如出一辙，只不过是存储了值

1
2
3
4
5
6
7
8
func tribonacci2(n int) int {
	res := make([]int, 0)
	res = append(res, 0, 1, 1)
	for i := 3; i <= n; i++ {
		res = append(res, res[i-3] + res[i-2] + res[i-1])
	}
	return res[n]
}