Вариант композиции с наибольшим сроком

Question

Я пытаюсь решить эту проблему Q5.https://utdallas.edu/~kyle.fox/courses/cs4349fa17/final.pdf Я думаю, что это вариант поиска композиции с наибольшим количеством частей.Значение dp, которое дает оптимальное решение (ответ на часть a), составляет

for each square:
      for each move:
           dp[squareno][moveno]=0
              for each move:
                     dp[square][moveno]=1+min(dp[squareno+moveno][move])

Сложность - тета (4 * 4 * n), где n - это число квадратов.Буду признателен, если вы посмотрите на решение и предложите некоторые изменения, чтобы сделать его правильным.

Answer 1

Нет необходимости в дополнительном состоянии move.Также цель состоит в том, чтобы максимизировать.

Цель игры - сделать как можно больше ходов до окончания игры.

Psuedocode:

dp[i] будет "Максимальное количество ходов, чтобы пересечь самый правый конец ряда квадратов от квадрата ih".Это будет -1 в случае, если его невозможно пересечь.

for square n..1:
   dp[i] = -1

   for all val in square i:
     if square+val > n:
       dp[i] = max(dp[i], 1)
       continue

     if dp[i+val] == -1:
       continue

     dp[i] = max(dp[i], 1 + dp[i+val])