dynamic-programming - 具有最大项的组合变体

Question

我正在尝试解决这个问题 Q5。 https://utdallas.edu/~kyle.fox/courses/cs4349fa17/final.pdf 我认为它是寻找具有最大零件数量的作品的一种变体。产生最优解（a）部分的答案的 dp 是

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

复杂度是 theta(4*4*n) 其中 n 是平方数。如果您查看解决方案并提出一些更改以使其正确，我将不胜感激。

标签： dynamic-programming

Answer 1

不需要额外的状态move。目标也是最大化。

游戏的目标是在游戏结束前尽可能多地移动。

伪代码：

dp[i]将是“从正方形 ith 穿过正方形行最右端的最大移动量”。-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])