Применение динамического программирования

Я готовлю интервью разработчиков программного обеспечения и пытаюсь понять, как применять динамическое программирование. Я знаю, что проблема должна соответствовать двум критериям - иметь оптимальную субструктуру и перекрывающиеся подзадачи. На примере, где у вас есть функция f (L), которая берет список целых чисел L и сопоставляет его с другим целым числом (например, f ([17, 5, 2, 12] = 35), как вы примените динамическое программирование к найти максимальное значение?

Пример

L = [17, 5, 2, 12, 9]

У вас может быть множество комбинаций f():

f([17]) + f([5]) + f([2, 12, 19])
f([17]) + f([5, 2]) + f([12, 19])

Я подошел к нему, вычислив f() для каждого элемента списка, например f ([17]). Тогда каждый из двух элементов, таких как f ([17, 5]), то каждый три элемента f ([5, 2, 12]) и т.д. Затем я отобразил эти значения в хеш-таблицу. Затем я попробовал все комбинации f(), чтобы найти максимальное значение. Я думаю, что этот подход не изящный и неловкий. Любые идеи о том, как подойти?

2 ответа

Типичным способом динамического программирования является создание функции, которая рекурсивно проходит через все допустимые перестановки подзадач, чтобы дать окончательный ответ, и сохраняя все ответы на подзадачи по мере продвижения (что называется memoization), поскольку эти субмастеры, вероятно, будут очень многократно использоваться повторно. В псевдокоде для примера проблемы:

function F(some_list) {
 ....
}
M = [[]]
L = [17, 5, 2, 12, 9]
function maximize(start, end) {
 // If we have already calculated the highest value
 // for the given slice, why do it again?
 if (M[start][end] != NULL) {
 return M[start][end]
 }
 // The function f applied to the whole slice we are
 // examining is also a viable solution, so we start
 // our hunt there
 max = F(L.slice(start, end))
 // If we are at an end node (that is, we can't
 // divide the problem into smaller pieces) we return
 // and save the value we just calculated
 if (end - start == 1) {
 M[start][end] = max
 return max
 }
 // Let look at all possible ways we can split the
 // slice we are currently examining
 for (split in range(start + 1, end - 1)) {
 // Let examine booth parts of the slice and see if
 // the sum of those solutions are better than our
 // previous best solution
 temp_max = maximize(start, split) + maximize(split, end)
 if (temp_max > max) {
 max = temp_max
 }
 }
 // We have examined all possible ways in which we can
 // slice and dice our slice, and found the best
 // solution. Yay! Let save it for future reference.
 M[start][end] = max
 return max
}
// Examine the whole list
the_great_maximum_value = maximize(0, L.length)


Вот один из возможных способов сделать это:

1) Определите dp[pos] как максимальное значение, которое можно получить, разбив первые pos элементы списка как-то (независимо от того, как).

2) Базовый регистр: dp[0] = 0. Это имеет место для пустого префикса.

3) для pos > 0:  dp[pos] = max(dp[prev_pos] + f(L[prev_pos + 1], L[prev_pos + 2], ..., L[pos])) для 0 <= prev_pos < pos.

4) Ответ dp[length(L)].

Сложность времени O(n^2 * time_to_comptute_f) (потому что мы перебираем все позиции в списке и для каждой позиции проверяем O(n) предыдущие позиции, вычисляя f каждый раз).

Сложность пространства O(n).

licensed under cc by-sa 3.0 with attribution.