Ошибка C2106: '=': левый операнд должен быть l-значением в последовательности Фибоначчи при динамическом программировании на C++

Question

Я пытаюсь написать программу для генерации последовательности Фибоначчи методом динамического программирования следующим образом.

#include<iostream>
#include<ctime>

int fib(int index)
{
    int memo[] = {0};
    memo[0] = 0;
    memo[1] = 1;
    for(int i = 2; i <= index; i++)
    {
        fib(index) = fib(index - 1) + fib(index - 2);   //error comes here
    }
    return fib(index);
}
int main()
{   
    time_t start, end, diff;
    int index;
    std::cout << "Please, enter the index of fibonacci sequence" << std::endl;
    std::cin >> index;
    start = time(NULL);
    std::cout << "calculating...." << std::endl << fib(index) <<std::endl;
    end = time(NULL);
    diff = (time_t)difftime(end, start);
    std::cout << "Time elapsed: " << diff << std::endl;
    return 0;
}

Но в линии fib(index) = fib(index - 1) + fib(index - 2); Я получаю ошибку как

error C2106: '=' : left operand must be l-value

Итак, скажите, пожалуйста, что я сделал не так в этой строке? Заранее спасибо.

Answer 1

Вы присваиваете значение l (что int fib(int) возвращается). Так же, как говорится в сообщении об ошибке.

Также обратите внимание, что int memo[] = {0}; создает массив размера 1так что писать за указателем 0 является недействительным.

Answer 2

Вы не можете назначить fib(index) как уже указывали другие. Существует обходной путь, возвращая ссылку или указатель.

Но сама программа ошибочна, так как входит в бесконечный цикл. Линия

fib(index) = fib(index - 1) + fib(index - 2);  

Сохраняет запуск fib(index), если index > 1. Правильный способ решения Фибоначчи с использованием DP

int fib(int n)
{
  int a = 0, b = 1, c, i;
  if( n == 0)
    return a;
  for (i = 2; i <= n; i++)
  {
     c = a + b;
     a = b;
     b = c;
  }
  return b;
}

Answer 3

Вы должны ввести временную переменную, подобную этой:

int result = 0;
for(int i = 2; i <= index; i++)
{
    result = fib(index - 1) + fib(index - 2);   //error comes here
}
return result;

Но это только техническое решение. Как указал Бала, ваш алгоритм как таковой не работает.

Это может быть решением, если вы ищете рекурсивное:

int fib(int index)
{
    switch(index) {
    case 0:
        return 0;
    case 1:
        return 1;
    default:
        return fib(index - 1) + fib(index -1);
    }
}

Для настоящего динамического решения вы должны сохранить все вычисленные значения в статической записке и использовать повторно, если она уже существует.

int fib(int index)
{
    // Stores fib for given index
    static std::map<int, int> memo;

    if (index == 0) return 0;
    else if (index == 1) return 1;
    else {
       auto it = memo.find(index);
       if (it == memo.end()) {
           int r = fib(index - 1) + fib(index -2);
           memo[index] = r;
       } else return *it;
    }
}