c++ - 如何在没有备忘录的情况下使用内存来执行此递归代码？

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

不知道怎么转化成memoization。我做过这样的事情:

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

下面我用 //* 标记了在您的代码中实现记忆化所需的更改。我假设代码是用 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;
}