Dynamic Programming Fibonacci Number

Question

I am trying to implement an approach using memoization for calculating the nth Fibonacci number.

#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);
}

However, I get this error.

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

How do I change the solution to resolve this problem? Thanks!

You also want to pass the vector by reference so that your memos are actually preserved instead of acting on a copy of the memo vector v. — Nathan Pierson
– Nathan Pierson, Commented Dec 3, 2020 at 23:04
And maybe switch to double instead of ints since you’re also having an integer overflow — Marouane Fazouane
– Marouane Fazouane, Commented Dec 3, 2020 at 23:06

Adrian Mole · Accepted Answer · 2020-12-06 18:53:41Z

3

You are copying the vector for each call, so you don't fill initial the vector by numbers.
You have to use unsigned long long to calculate more numbers (actually 93 of them). int can fit only 46 (1836311903).
I would check the vector size inside of the function instead of creating it outside.

Use

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

Full code: 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;
}

edited Dec 6, 2020 at 18:53

Adrian Mole

52.1k193 gold badges61 silver badges101 bronze badges

answered Dec 3, 2020 at 23:06

Qwertiy

21.9k17 gold badges69 silver badges143 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

Dynamic Programming Fibonacci Number

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related