递归解法在动态规划中的应用

Question

可能重复：
动态规划和背包问题应用 我一直在尝试理解动态规划，但每次遇到新的问题时，我都会对如何编写递归函数感到有些困惑。

以以下问题为例： 有一张 L×H 的金属板，可以通过机器垂直或水平切割成两部分。L、H 都是整数，切割也发生在整数值上。有 n 种矩形图案，每个矩形图案 l(i)×h(i)，i≤n（l、h 也是整数），其中第 i 个图案的利润为 c(i)。设计一个有效的算法，以在切割板材的同时最大化总利润。

现在我认为为了解决这个问题，我们需要创建一个 LxH 的表格（该表格将被对角线填充）。但是，我们如何形成递归以解决这个问题呢？

- user978278

---

你应该从一个递归的 O(2^n) 解决方案开始，并思考如何将其优化成一个多项式解决方案，而不是相反地去做。 - jli

@jli 我该如何开始解决这个问题？ - user978278

同样的问题在这里：https://dev59.com/vmjWa4cB1Zd3GeqPvfL8 - Haile

动态规划问题可以通过递归来解决，因为每个不是基本情况的实例都可以使用动态规划和一些额外的步骤来解决。这与递归的区别并不清楚。您确定这不是作业吗？ - Marc van Dongen

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
)

- Juan Lopes

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

- user586399