动态规划的递归解决方案

Question

可能的重复项：
动态编程和背包应用

我一直在尝试理解动态编程，但是对于每个新问题，我对如何为其编写递归感到有些困惑。

以以下问题为例：有一个L×H金属板，可以通过机器垂直或水平切割成两块。L、H 都是积分，切割也沿着积分值发生。有 n 个矩形形态 l（i） × h（i） ， i ≤ n（l， h 也是积分），其中第 i 个形态有利润 c（i）。 设计一种有效的算法来切割纸张，从而最大化总利润。

现在我认为为了解决它，我们将创建一个 LxH 表（将对角填充）。但是我们如何形成递归来解决这个问题呢？

Answer 1

我会尝试对每个 T（L， H） 进行类似操作，验证以下两者之间的最佳替代方案：

• 立即收取利润
• 水平切割各种可能的方式
• 垂直切割各种可能的方式

像这样：

T(L, H) = max(
    c(L, H),  
    T(i, H)+T(L-i, H), // 0<i<L
    T(L, i)+T(L, H-i)  // 0<i<H
)

Answer 2

我不

明白为什么你真的想在你有 dp 关系时使用递归。回溯递归通常效率非常低，因为它的复杂性通常为 O（2^N） 或更高。

但是，这些指数算法很像这样：

function rec(state)
    if state = end
       return
    Choose the current element
    rec(state + 1)
    Don't choose the current element
    rec(state + 1)

在您的情况下，这可能是类似于此蛮力：

  function rec(rect r)
      if r is empty
        return 0
      Max = 0
      for i = 1 to r.width
          for j = 1 to r.hight
             rect g = cut(r, i, j)
             Max = max(Max, profit(g) + rec(r - g))
      return Max