Упражнение на динамическое программирование

Question

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

Нам дается 2 последовательностей u1,u2,...,un и d1,d2,...,dm и матрицу размеров n x m, построенные из натуральных чисел C=[cij]. Список k пар ((ui1, dj1),(ui2,dj2),...,(uik,djk)) считается непересекающимся, если i1 < 12 <..< ik и j1 < j2 <...< jk. «Совместимостьс из списка» называется совместимость суммы пар, что он сделан из, то есть Ci1j1 + Ci2j2 + ... + Cikjk

Пример: Рассмотрим матрицу C = [Cij], поэтому Cij = squared(i + j). Пусть i будет i = 1, 2, 3, j = 1, 2, 3, 4 и k = 2. Некоторые списки из двух непересекающихся пар - это ((u1, d2),(u3, d3)) с совместимостью 9 + 36 = 45, ((u2, d2),(u3, d4)) с совместимостью 16 + 49 = 65, и ((u1, d1),(u2, d4)), с совместимостью 4 + 36 = 40. Некоторые списки, которые не являются непересекающихся являются следующие: ((u2, d2),(u3, d1)),((u1, d4),(u3, d3)),((u3, d2),(u2, d3))

Решение:

М (I, J, T) = максимальная стоимость т непересекающихся пар взяты из щ, ..., ип и ди-джей, ... дм

Рецидив уравнение:
M(i, j, t) = max {M(i + 1, j + 1, t − 1) + c(i, j), M(i, j + 1, t),M(i + 1, j, t).}

• M(i, j, 0) = 0
• M(i, j, t) = −∞, if t > min{n − i + 1, m − j + 1}
• M(i, j, t) = 0, if i > n or j > m

Я не под reccurrence очень хорошо, и почему мы относим −∞ к M(i, j, t) когда t > min{n − i + 1, m − j + 1} но 0, когда i > n или j > m

Раствор М (1, 1, к) ,

Answer 1

M(i, j, t) = max {M(i + 1, j + 1, t − 1) + c(i, j), M(i, j + 1, t),M(i + 1, j, t).} 
      = max 
      { 
       M(i+1, j+1, t-1) + c(i, j), <- we know the maximum cost of t-1 
               non-intersecting pairs taken from 
               i+1,...,n and j+1,...,m to which 
               we prepend the pair (i, j). 
       M(i, j+1, t), <- keep it at t elements and don't prepend anything, 
            and take the one containing elements from 
            i,...,n and j+1,...,m 
       M(i+1, j, t) <- same, but take elements from i+1,...,n and j,...,m 
      } 

Это охватывает все случаи: либо предварять текущий элемент и увеличить длину на 1 или мы не увеличивать длину и взять максимум из возможностей этого (отсутствие) действие влечет за собой. Вы можете спросить «но как насчет M(i+1,j+1,t)?», Это также допустимая возможность ». Это, но оно покрыто двумя другими случаями: M(i+1,j,t) проверит M(i+1,j+1,t) и вернет его, если потребуется. Вы могли бы добавить его к повторению, это было бы неправильно, просто избыточно.

почему мы относим -∞ М (I, J, т) при т> тт {п - г + 1, т - J + 1}

Потому что вы не можете иметь решение в таком случае. На шаге i вы можете выбрать только n - i + 1 элементов из первой последовательности (потому что вы уже подобрали до i). То же самое для j. Если t > min{n - i + 1, m - j + 1}, то вы не сможете выбрать необходимое количество элементов из одного из списков, и вы отметите это с отрицательной бесконечностью.

но 0, когда я> п или J> м

Это только для обработки из-за ошибок диапазона. Я не уверен, почему они выбирают 0, я бы выбрал отрицательную бесконечность для этого, а просто для согласованности, или просто избегаю его вообще, поставив условия в реализацию (если i + 1 >= n, то проигнорируйте эту ветку, хотя вам все равно придется возвращать 0/-infinity, если ни одна из ветвей не действительна), но это не имеет большого значения.

Если вы вернетесь 0 и ответ отрицательный, тогда у вас возникнут проблемы. Конечно, для вашей проблемы из-за способа построения C у нас не может быть отрицательного решения (потому что C содержит квадраты чисел, которые всегда равны >= 0). Таким образом, вы можете пойти с 0 вместо отрицательной бесконечности в первом случае.

Упражнение: Вы можете написать аналогичный рекуррент, но для которого решение задано M(n, m, k)? Определите это в словах сначала, а затем математически.