动态规划斐波那契数

Question

我正在尝试实现一种使用记忆来计算第 n 个斐波那契数的方法。

#include <iostream>
#include <vector>
using namespace std;

int fib(int n, vector<int> v) {
    int result = 0;
    if (v[n] != 0) {
        return v[n];
    }

    if (n == 1 || n == 2) {
        result = 1;
    }
    else {
        result = fib(n - 1, v) + fib(n - 2, v);
    }

    v[n] = result;
    return result;
}

int main()
{
    int n = 12;
    vector<int> v(n + 1, 0);

    cout << fib(n, v);
}

但是，我得到了这个错误。

runtime error: addition of unsigned offset to 0x602000000110 overflowed to 0x60200000010c (stl_vector.h) SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior /usr/bin/../lib/gcc/x86_64-linux-gnu/9/../../../../include/c++/9/bits/stl_vector.h:1043:34

如何更改解决方案来解决此问题？谢谢！

Answer 1

您正在为每个调用复制向量，因此您不会用数字填充向量的初始值。
您必须使用 unsigned long long 来计算更多数字（实际上是 93 个）。 int 只能容纳 46 (1836311903)。
我会在函数内部检查矢量大小，而不是在外部创建它。

使用

unsigned long long fib(int n, vector <unsigned long long> &v) {

完整代码：https://ideone.com/3Ipjgo

#include <iostream>
#include <vector>

using namespace std;

unsigned long long fib(int n, vector <unsigned long long> &v)
{
  if (v.size() <= n)
    v.resize(n + 1);

  if (v[n])
    return v[n];

  return v[n] = n <= 2 ? 1 : fib(n - 1, v) + fib(n - 2, v);
}

int main()
{
  vector <unsigned long long> v;

  cout << fib(12, v) << endl;

  for (int q=1; q<=94; ++q)
    cout << q << ' ' << fib(q, v) << endl;
    
  return 0;
}

动态规划斐波那契数

Dynamic Programming Fibonacci Number

c++

recursion

dynamic-programming

fibonacci