斐波那契数列

1、递归方法

通过记录已经算出的值，减少重叠计算

package main

import "fmt"

func fib(n int) int {
    if n < 1 {
        return 0
    }
    s := make([]int, n+1)
    return helper(&s, n)
}

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

func main() {
    fmt.Println(fib(8))
}

上面方法通过一个切片，记录已经算出来的斐波那契数，避免递归当中重复计算子问题。

2、动态规划方法

package main

import "fmt"

func fib(n int) int {
    s := make([]int, n+1)
    s[1], s[2] = 1, 1
    for i := 3; i <= n; i++ {
        s[i] = s[i-1] + s[i-2]
    }
    return s[n]
}

func main() {
    fmt.Println(fib(6))
}

动态规划：根据已知的数自底向上计算出后面的费波纳契数
递归方法：自顶向下先计算后面的，然后递归到已知的小斐波那契数。
两种方法的复杂度都是O(n)。
动态规划的方法中，可以进一步优化空间复杂度，因为我们这里只需要保存每个数的前两个已经计算出的斐波那契数即可，所以：

package main

import "fmt"

func fib(n int) int {
    if n <= 2 {
        return 1
    }
    cur := 1
    pre := 1
    for i := 3; i <= n; i++ {
        cur, pre = (cur + pre), cur
    }
    return cur
}

func main() {
    fmt.Println(fib(6))
}