//递归，超出限制
func fib(n int) int {
    if n == 1 {
        return 1
    }else if n <= 0 {
        return 0
    }else{
        sum := 0
        for{
            sum += fib(n-1) + fib(n-2)
        }
        return (fib(n-1) + fib(n-2) ) % 1000000007
    }
}
//动态规划
func fib(n int) int {
    if n==0 ||n==1{
        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])%1000000007
    }
    return dp[n]
}