斐波那契数列

我的妈呀，一道题折磨我一个小时了
题目描述：
形如1, 1, 2, 3, 5, 8, 13, 21, 34, 55的数列，后一位是前面两位相加（斐波那契数列），写出函数要求找到第 N 位是多少，如：fib(3) => 3 ， fib(5) => 8, 要求时间复杂度为O(n)。

输入描述:
输入一个正整数N（0<=N<=50）
输出描述:
输出第n项的数值

示例1：
输入3
输出3

注意到和剑指offer的区别了嘛，本题的斐波那契数列是从1开始的，而我们所知道的都是从0开始的。
而且这个的N的范围是0-50，在N=50的时候是一个超出int范围的数，那时候该怎么处理呢。

第一个代码：模仿动态规划的DP Table

#include<iostream>
#include<vector>
using namespace std;
int main()
{
    int n;
    cin>>n;
    if(n==1)return 1;
        vector<long long> dp(n+2,0);
        dp[1]=1;
        for(int i=2;i<=n+1;i++)
            dp[i]=dp[i-1]+dp[i-2];
        cout<<dp[n+1];
    return 0;
}

第二种代码

#include<iostream>
#include<vector>
using namespace std;
long long help(int n) {
    if (n == 1) return 1;
    vector<long long> result(n + 2, 0);
    result[1] = 1;
    for (int i = 2; i <= n+1; ++i) {
        result[i] = result[i - 1] + result[i - 2];
    }
     return result[n+1]; 
}

int main()
{
    int n;
    cin >> n;
    long long result = help(n);
    cout << result;
    return 0;
}

越努力，越幸运。