Рекуррентное соотношение для упражнений с динамическим программированием

Question

Я получил динамическое программирование, и мне нужна помощь в выяснении отношения повторения. Проблема аналогична взвешенная задача интервальной, но имеет несколько дополнительных ограничений:

• Вам предоставляется ряд N временных интервалов, каждый из той же продолжительности.
• Каждому слоту k, 0 <= k < N, предоставляется положительный вес W[k].
• Для любого временного интервала [i, j] с i < j, вес W[i,j] этого интервала является:
  W[i,j] = W[i+1] + W[i+2] + ... + W[j]
  Обратите внимание, что вес W[i] первого временного интервала не учитывается, следовательно, любой интервал длины 1 имеет вес 0.

Вам даны значение T < N и попросили выбрать именно T временные интервалы, так что сумма выбранных временных интервалов максимизируются.

Пример: Для N = 5, T = 4 и весов W = (3, 9, 1, 1, 7), выбирая W[0, 1] = 9 и W[3, 4] = 7 даст максимальный вес 16.

Answer 1

Это хорошая небольшая проблема ... Определите S (i, t) как максимальный вес, если выбран последний слот (конец последнего диапазона), равный i, а среди слотов 0..i есть точно t слотов.

Решение DP состоит в том, что мы либо добавляем w [i] в ​​S (i, t), либо не потому, что выбран либо слот i-1, либо он не был. Таким образом, мы имеем:

S(i, t) = max (S(i-1, t-1) + w[i], S(j, t-1) for j = t-2..i-2) 

Случаи, где t-1> i бессмысленны. Таким образом, базовый случай равен S (i, 1) = 0 для 0 < = i < N, а последовательные столбцы (t = 2, ..., T) таблицы DP кажутся короче последнего. Желаемый ответ макс (S (j, T) для j = T-1..N-1)

К счастью, вы можете организовать вычисление так, чтобы максимы вычислялись постепенно, время выполнения - O (NT), и пространство O (N)

Разработка ваш пример, таблица DP выглядит следующим образом:

   t = 
     1 2 3 4 
     ------------------ 
i = 0 | 0 
    1 | 0 9 
    2 | 0 1 10 
    3 | 0 1 9 11 
    4 | 0 7 9 16 

ответ макс (11, 16) = 16