使用动态规划 n = 656 第 N 个斐波那契数的错误答案

Question

class Solution {
  public:
  
    
    long long int nthFibonacci(long long int n){
        // code here
        //TABULATION
        long long int lookup[1001];
        lookup[0]=0;
        lookup[1]=1;
        for(long long int i=2;i<=n;i++){
            lookup[i]=lookup[i-1]+lookup[i-2];
        }
        return (lookup[n]%1000000007);
    }
};

当我在 GFG 上提交它时，它显示您的代码给出了 n=656 的错误输出

答案错误。 !!!错误答案

您的代码可能无法正确处理多个测试用例 (TC)。

您的代码失败的第一个测试用例：

输入： 656

它的正确输出是： 823693831

你的代码的输出是： -584713349

Answer 1

更新：找到了问题的正确解决方案，但仍然不知道我之前的代码有什么问题如果有人可以看看正确的解决方案并指出我的错误..提前致谢！正确答案：

class Solution {
  public:
  
    
    long long int nthFibonacci(long long int n){
        // code here
        //TABULATION
        const long long int mod=1000000007;
        long long int lookup[1001];
        lookup[0]=0;
        lookup[1]=1;
        for(long long int i=2;i<=n;i++){
            lookup[i]=(lookup[i-1]%mod+lookup[i-2]%mod)%mod;
        }
        return lookup[n];
    }
};

Answer 2

斐波那契数列增长得相当快。

fib(n) / (pow(phi, n)) -> 1/sqrt(5) as n -> infinity
where phi is the golden ratio, phi ~= 1.618

这意味着 fib(n) 需要大约

n*log2(phi)-0.5log2(5) ~ 0.694*(n-2) bits.

所以 fib(656) 需要大约 452 位。 long long int 不可能那么大！

在您的原始代码中，long long int 的 table 无法为较大的斐波那契数提供正确的结果。

在 C（我认为是 C++）中，检测和纠正溢出很困难。最好确保它永远不会发生。在您的情况下，您只需要斐波那契数 mod m (m=1000000007)。因此，您可以用斐波那契数 mod m 填充 table。由于 m 适合 32 位，因此所有数字 modulo 以及它们中的两个之和适合 32 位，因此不会发生溢出。

顺便说一下，您修改后的代码中有一些冗余的 mod；你可以

for(long long int i=2;i<=n;i++){
    lookup[i]=(lookup[i-1]+lookup[i-2])%mod;
}

因为当你使用它时 lookup[i-1] 已经减少了 mod m.

使用动态规划 n = 656 第 N 个斐波那契数的错误答案

Wrong Answer for n = 656 Nth Fibonacci Number using Dynamic Programmin

recursion

dynamic-programming

fibonacci

recurrence