Я новичок в программировании Dynami c. Я не могу определить один из общих шаблонов (по словам автора) на сайте https://leetcode.com/discuss/general-discussion/458695/dynamic-programming-patterns.
Часть, в которой у меня возникла проблема, -
Принятие решений
Общая постановка проблемы для этого шаблона - это прощенная ситуация: решить, использовать или не использовать текущее состояние. Итак, проблема требует, чтобы вы приняли решение в текущем состоянии.
Заявление
Для заданного набора значений найдите ответ с возможностью выбора или игнорирования текущего значения.
Подход
Если вы решили выбрать текущее значение, используйте предыдущий результат, в котором значение было проигнорировано; наоборот, если вы решите игнорировать текущее значение, используйте предыдущий результат, в котором использовалось значение.
// i - indexing a set of values
// j - options to ignore j values
for (int i = 1; i < n; ++i) {
for (int j = 1; j <= k; ++j) {
dp[i][j] = max({dp[i][j], dp[i-1][j] + arr[i], dp[i-1][j-1]});
dp[i][j-1] = max({dp[i][j-1], dp[i-1][j-1] + arr[i], arr[i]});
}
}
Пожалуйста, помогите мне понять, что это означает и как работает. Это будет большим подспорьем.
(я прокомментировал сообщение, но не получил ответа).