3

我正在努力解决我无法解决的动态编程任务。当您被要求计算解决方案的数量时，我在一本书中发现了一个类似的问题，并且它说这是一个计数问题而不是优化问题，这很明显。我想要一个如何处理这类任务的建议，我想知道是否有一个通用的方法来解决这个问题。我想知道这里的递归关系以及哪些是子问题。这是问题所在：

你有 n 个地方来放置你的立方体。最少三个连续的立方体被视为一个图形。数字至少由一个位置分隔。您被要求计算所有可以将数字放置在空闲位置上的方式。这是 n = 7 的解决方案。蓝色方块代表放置立方体的空闲位置，红色方块代表立方体。路数等于 17。

4

2 回答 2

2

@saeedn 几乎得到了它，但他的递归公式并不完全正确，因为它有一些缺失的情况和一些重复计算。

让我们首先检查一下可能性，要么是空间（单个空间），要么那里有一个图形。图形的长度可以是 3,4,...,n-1,n。
如果小于 then n，我们还需要在下一个图形之前添加“填充”（以避免重复计算），所以如果我们有一个 3 个立方体的图形，它有f(n-4)不同的可能性（前 3 个单元格是立方体）。一个例外是n节点图，因为我们不能在它之后添加“填充”。

另一种可能性是单个空格，如果有更多空格，递归将在稍后处理它。

这给了我们以下递归公式：

f(0) = f(1) = f(2) = 1 (base)
f(n) = f(n-4) + f(n-5) + ... + f(1) + f(0) +   f(0)      + f(n-1)
         ^        ^             ^       ^       ^             ^
         3        4             n-2     n-1      n           space
       cubes    cubes          cubes    cubes   cubes
         +         +             +       +        +
        space    space         space    space   space

因此，如果我们将这个公式应用于 DP 算法，我们将得到：

arr[n+1] = [0,0,...,0]
arr[0] = arr[1] = arr[2] = 1
for (int i = 3; i < n+1; i++) 
   for (int j = 0; j <= i - 4; j++)  //f(n-4) + f(n-5) + ... + f(1) + f(0)
      arr[i] += arr[j]
   arr[i] += arr[0] // extra one f(0) for a shape with i cubes
   arr[i] += arr[i-1] // space
return arr[n]
于 2013-08-07T18:54:25.507 回答
0

为了在这类问题中找到递归关系，你应该考虑一个可能的位置，比如在你的位置的开始，看看你如何能把剩下的位置看作是一个像最初的问题一样的问题，但尺寸更小。

例如在这个问题中，从左边开始，您可以将一个图形放置在第 1、2、...、nL 号位置（其中 L 是图形的大小），并将该图形右侧的其余空间处理（不包括一个分隔空间）与较小的尺寸相同的问题。

如果我们想制定递归，我们可以这样写：

F(n) = sum [L=3 to n] (sum [p=0 to nL] (F(npL-1)))

其中 L 迭代图形大小， p 迭代放置该图形的位置（从左开始）。

如需详细说明：

(putting figure of size of 3)
###---- (we spent 3 spaces and reserve one space for separator,
         thus we have n-4 spaces which can be filled in F(n-4) ways)
-###--- (putting the figure in next available space => F(n-5) for the rest)
...
----###

(now putting figure of size 4)
####--- (F(n-(4+1)) = F(n-5) ways for empty spaces)
...

(and so on)
于 2013-08-07T18:32:36.653 回答