使用动态编程的n=656第n个Fibonacci数的错误答案

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

斐波那契数增长非常快。

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个比特。长整型不太可能有那么大！

在原始代码中，长整型的表无法保存较大fibonacci数的正确结果。

在C(我认为C++(中，检测和纠正溢出是很困难的。最好确保它永远不会发生。在您的情况下，您只需要斐波那契数mod m(m=1000000007(。因此，你可以用斐波那契数mod m来填充表格。由于m适合32位，所以所有数字都将其取模，其中两个数字的和适合32位。因此不会发生溢出。

顺便说一句，你在修改后的代码中有一些多余的mod；你可以有

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

因为当你使用它查找[i-1]时，已经减少了模式m。

Answer 2

Update:找到了问题的正确解决方案，但仍然不知道我以前的代码出了什么问题如果有人能看看正确的解决方案并指出我的错误。。提前感谢！！正确的解决方案：

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];
}
};