题解 | #斐波那契数列#

package main

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param n int整型 
 * @return int整型
*/
func recursion(i int, dp []int) int {
	if i == 1 || i == 2 {
		return 1
	}
	if dp[i] != 0 {
		return dp[i]
	}
	t1 := recursion(i-1, dp)
	t2 := recursion(i-2, dp)
	dp[i] = t1 + t2
	return dp[i]
}

// 方法2:使用动态规划记录当前的最优解值；不要每次都重复计算
func Fibonacci(n int) int {
	// write code here
	dp := make([]int, n+1)
	return recursion(n, dp)
}