Как выбрать начальные значения кеша в динамическом программировании?

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 в качестве типа элемента, и пустое значение представляет некэшированное значение.

Answer 2

Есть и другие подходы, которые вы можете использовать. Если вы хотите придерживаться подхода, к которому вы привыкли, этот вопрос не столько о динамическом программировании, сколько о значениях дозорного . Какое значение вы можете использовать в качестве дозорного, если возможны все действительные числа?

Одна деталь, которую я замечаю, состоит в том, что возможны все действительные числа. Это и хорошо, и плохо. Это плохо, потому что компьютер не может представить каждое действительное число, но, вероятно, это уже учтено. Это хорошо, потому что большинство методов, используемых для представления действительных чисел, включают некоторые значения, которые не являются действительными числами. float или double значения, которые, очевидно, не являются действительными числами, являются NaNs (не число). Другой вариант - бесконечность . В любом случае, std::is_finite можно использовать для определения того, было ли изменено значение дозорного до действительного числа.

Строго говоря, не гарантируется, что эти значения будут доступны, но на практике они, вероятно, есть. Когда они доступны, их можно использовать в качестве часовых, если ваша специальная функция не может их вернуть. (Дважды проверьте утверждение «возможны все действительные числа» в терминах float / double значений & mdash; может ли функция вернуть значение, которое не является действительным числом?)

Answer 3

Вы можете иметь логический массив. Если вы когда-то рассчитывали для (i, j), сохраняйте истинное значение для этого логического [i] [j]. Поэтому, когда вы проверяете, является ли это состояние префиксированным или нет, просто проверяйте, является ли boolean [i] [j] истинным или нет. Если true, то возвращает хранимое значение из массива таблицы.

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