algorithm - 动态规划任务/计数问题

Question

我正在为一个我无法解决的动态规划任务而苦苦挣扎。当你被要求计算解决方案的数量时，我在一本书中发现了一个类似的问题，它说这是一个计数问题而不是优化问题，这是显而易见的。我想要一个如何处理这类任务的建议，我想知道是否有一个通用的方法来解决这个问题。我想知道这里的递归关系以及哪些是子问题。这是问题所在:

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

Answer 1

@saeedn 几乎搞定了，但是他的递归公式不太正确，因为它有一些遗漏的情况和一些重复计算。

让我们检查一下第一个位置的可能性，要么是一个空格(单个空格)，要么那里有一个图形。图的长度可以是 3,4,...,n-1,n。
如果小于n，我们还需要在下一个数字之前添加'padding'(避免重复计算)，所以如果我们有一个3个立方体的数字，它有f(n-4) 不同的可能性(前 3 个单元格是立方体)。 n 节点的图是个异常(exception)，因为我们不能在它后面添加“填充”。

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

这为我们提供了以下递归公式:

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]