Как сделать этот рекурсивный код без памятки, с memoization?

Question

Я знаю, что запоминание, но имея этот рекурсивный код:

int F(int n , int T){ 

    int ganancia ; 
    int maximum = INT_MIN; 



    if(T >= 0 && n == 0){ 

     maximum = 0; 

    }else if(T < 0){ 

     maximum = INT_MIN; 

    } else if(T >= 0 && n > 0){ 

     for(int i = 0 ; i <= m[n-1] ; i++){ 

      ganancia = i*v[n-1] + F(n- 1,T- i*t[n-1]); 

       if(ganancia > maximum){ 

        maximum = ganancia; 

       } 
     } 
    } 

    return maximum; 
} 

Я не знаю, как превратить в запоминание. Я сделал что-то вроде этого:

int F_alm(int n, int T){ 

    int ganancia ; 
    int maximum = INT_MIN; 

    //PETA POR ESTO 
    if(almacen_rec[n-1][T] != -1){ 

     return almacen_rec[n-1][T]; 

    }else if(T >= 0 && n == 0){ 

     maximum = 0; 

    }else if(T < 0){ 

     maximum = INT_MIN; 

    } else if(T >= 0 && n > 0){ 

     for(int i = 0 ; i <= m[n-1] ; i++){ 

      ganancia = i*v[n-1] + F(n- 1,T- i*t[n-1]); 

       if(ganancia > maximum){ 

        maximum = ganancia; 

       } 
     } 
    } 

    almacen_rec[n-1][T] = maximum; 
    return maximum; 

} 

Цель состоит в том, чтобы иметь переменную almacen_rec (она инициализируется ранее все как -1), как это изображение:

Я оставляю вам общую функцию упражнения :

Благодарим за помощь!

Answer 1

Ниже я отметил изменения, необходимые для реализации memoization в вашем коде с помощью // *. Я предполагаю, что код находится на C++, поэтому я могу использовать std::pair и std::map из стандартной библиотеки.

std::map<std::pair<int, int>, int> table; // * (A global variable) 

int F(int n , int T){ 

    // See if we've already computed this value 
    std::pair<int, int> pair(n, T); // * 
    if (table.find(pair) != table.end()) { // * 
     return table[pair]; // * 
    } // * 

    int ganancia ; 
    int maximum = INT_MIN; 



    if(T >= 0 && n == 0){ 

     maximum = 0; 

    }else if(T < 0){ 

     maximum = INT_MIN; 

    } else if(T >= 0 && n > 0){ 

     for(int i = 0 ; i <= m[n-1] ; i++){ 

      ganancia = i*v[n-1] + F(n- 1,T- i*t[n-1]); 

       if(ganancia > maximum){ 

        maximum = ganancia; 

       } 
     } 
    } 
    // Store the value so we won't have to compute it again later if needed 
    table[pair] = maximum; // * 
    return maximum; 
}