斐波那契数列

斐波那契数列

https://leetcode-cn.com/problems/fibonacci-number/

带备忘录的递归

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
func fib(n int) int {
    memo := make([]int, n + 1)
    return helper(memo, n)
}

func helper(memo []int, n int) int {
    if n == 0 || n == 1 {
        return n
    }
    if memo[n] != 0 {
        return memo[n]
    } else {
        memo[n] = helper(memo, n - 1) + helper(memo, n - 2)
        return memo[n]
    }
}

动态规划

直接构建 DP 数组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
func fib(n int) int {
    // base case
    if n == 0 || n == 1 {
        return n
    }

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

    for i := 2; i < len(dp); i++ {
        dp[i] = dp[i - 1] + dp[i - 2]
    }

    return dp[n]
}