509. 斐波那契数

509. 斐波那契数

递归

func fib(N int) int {
    if N<2{
        return N
    }
    return fib(N-1)+fib(N-2)
}

迭代

func fib(N int) int {
    if N<2{
        return N
    }
    var v1 =0
    var v2 =1
    for i:=2;i<=N;i++{
         tmp := v1+v2
        v1 = v2
        v2 = tmp
    }
    return v2
}

动态规划

func fib(N int) int {
    if N<2{
        return N
    }
    dp := make([]int,N+1)
    dp[0] = 0
    dp[1]= 1
    for i:=2;i<=N;i++{
        dp[i] = dp[i-1]+dp[i-2]
    }
    return dp[N]
}

优化动态

func fib(N int) int {
    if N<2{
        return N
    }
    pre := 0
    curr := 1
    for i:=2;i<=N;i++{
        sum :=pre+curr
        pre = curr
        curr = sum
    }
    return curr
}