c++ - 动态规划中如何选择缓存的初始值？

Question

每当我使用动态编程编写带有解决方案的代码时，我的代码看起来像这样:

table[1000][1000]  //the cache to store initialized with a certain_value
function(parameters i,j){
    if(base_condition){
        return base_value
    }
    if(table[i][j] != certain_value){
        return table[i][j];
    }
    answer = some operation using function();
    table[i][j] = answer;
    return answer;
}

通常我选择这个certain_value作为-1。但是现在我正在编写一个函数可以返回所有实数的代码。那么我该如何选择这个值，或者我应该改变我的方法。

Answer 1

您可以使用 bool 元素的并行数据结构来表示哪些元素已被缓存。

或者，您可以使用 std::optional 作为元素类型，并让空值表示非缓存值。