题解 | #斐波那契数列#

package main

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

// fib(1) = 1
// fib(2) = 1
// fib(3)  = fib(3-1) + fib(3-2) = 2
// fib(x) x = 1,2   fib(x) = 1
// fib(x) x >= 3    fib(x) = fib(x-1) + fib(x-2)

/**
func Fibonacci( n int ) int {
    // write code here
    if n <= 2 {
      return 1
    }
    return Fibonacci(n - 1) + Fibonacci(n -2)
}
*/