金字塔动态规划

Question

面试遇到这个问题，想不通。我相信它有一个动态规划解决方案，但它让我望而却步。

给定一些砖块，输出可能的 2d 金字塔总数，其中金字塔被定义为任何结构，其中一行砖块的砖块数量严格少于其下一行。您不必使用所有积木。

一块砖就是一个正方形，一排砖的数量是唯一重要的信息。

真的坚持这个，我认为迭代和求和解决每个问题 1...n 会很容易。但是想出恰好有 i 块砖可能建造的金字塔数量让我望而却步。

例子，n = 6

X

XX

X
XX   XXX

X
XXX   XXXX

XX      X
XXX   XXXX   XXXXX

X
XX      XX       X
XXX   XXXX   XXXXX   XXXXXX

所以答案是用 6 块积木拼出 13 个可能的金字塔。

编辑

我肯定这是一个动态规划问题，因为（一旦你确定了第一行）只需查看你记忆的剩余砖块数组中的索引，看看有多少金字塔适合在上面。

考虑底部行的宽度至少 n/2 也是有意义的，因为我们不能在顶部放置比底部行更多的砖块 EXCEPT 这是在我失去它并且我的思想崩溃的地方，在某些（少数情况下）你可以，即N = 10

X
XX
XXX
XXXX

现在底行有 4 个，但还有 6 个要放在上面

但是当 n = 11 时，我们的底行不能少于 n/2 块砖。还有另一个奇怪的不一致，比如 n = 4，我们不能在底行设置 n/2 = 2 块砖。

Answer 1

您可以用多少种方法构建宽度为 n 的金字塔？通过将任何宽度为 n-1 或更小的金字塔放置在 n 砖层之上的任意位置。所以如果 p(n) 是宽度为 n 的金字塔数，那么 p(n) = sum [m= 1 到 n-1] (p(m) * c(n, m))，其中 c(n, m) 是您可以放置的方式数在宽度 n 的层上一层宽度 m （我相信你可以自己解决这个问题）。

然而，这并不限制积木的数量。通常，在 DP 中，任何资源限制都必须建模为一个单独的维度。所以你现在的问题是 p(n, b): "How many pyramids can you build of width n with a total of b bricks"?在递归公式中，对于在当前金字塔顶上建造较小金字塔的每种可能方法，您需要参考剩余砖块的正确数量。我把计算递归公式作为一个挑战留给你；如果您需要任何提示，请告诉我。

Answer 2

您可以将您的递归视为：给定 x 块剩余的砖块，您在最后一行使用 n 块砖块的地方，您可以建造多少座金字塔。现在您可以从上到下或从下到上填充行。我会解释前一种情况。
这里的递归可能看起来像这样（left 是剩余的砖块数量，last 是最后一行使用的砖块数量）

f(left,last)=sum (1+f(left-i,i)) for i in range [last+1,left] inclusive.

因为当您在当前行使用 i 块积木时，您将剩下 left-i 块积木，i 将是该行使用的积木数。

代码：

int calc(int left, int last) {
    int total=0;
    if(left<=0) return 0;  // terminal case, no pyramid with no brick
    for(int i=last+1; i<=left; i++) {
        total+=1+calc(left-i,i);
    }
    return total;
}

我将留给您实施 memoized 或 bottom-up dp 版本。此外，您可能希望从底行开始并填满金字塔中的上行。

Answer 3

让我们选择一个合适的定义：

f(n, m) = # pyramids out of n bricks with base of size < m

你现在要找的答案是（假设N是你输入的砖块数）：

f(N, N+1) - 1

让我们分解一下：

第一个N很明显：那是你的积木数量。
您的底行最多包含 N 个积木（因为您只有这些），因此 N+1 是一个足够的下限。
最后，- 1 在那里，因为从技术上讲，空金字塔也是金字塔（因此将被计算在内），但您将其从解决方案中排除。

基本情况很简单：

f(n, 0) = 1   for any n >= 0
f(0, m) = 1   for any m >= 0

在这两种情况下，我们在这里计算的都是空金字塔。

现在，我们所需要的只是一般情况下的递归公式。

假设给定 n 和 m 并选择在底层放置 i 块砖。我们可以在这一层之上放置什么？一个较小的金字塔，我们还剩下 n - i 块砖，其底部的大小为 < i。这正是 f(n - i, i).

i 的范围是多少？我们可以选择一个空行，所以 i >= 0。显然，i <= n 因为我们只有 n 个积木。而且，根据 m.

的定义，i <= m - 1

这导致递归表达式：

f(n, m) = sum f(n - i, i) for 0 <= i <= min(n, m - 1)

您可以递归地计算 f，但是使用动态规划当然会更快。虽然存储结果矩阵很简单，所以我把它留给你。

回到最初的说法，f(N, N+1)-1 是您正在寻找的答案，为 m 选择哪个值并不重要，只要它是 > N.基于递归公式，很容易证明 f(N, N + 1) = f(N, N + k) 对于每个 k >= 1:

f(N, N + k) = sum f(N - i, i) for 0 <= i <= min(N, N + k - 1)
            = sum f(N - i, i) for 0 <= i <= N
            = sum f(N - i, i) for 0 <= i <= min(N, N + 1 - 1)

Answer 4

由于我们被要求计算任何小于或等于 n 的基数的金字塔，我们可以依次考虑每个基数（1 个元素、2 个元素、3 等的金字塔）和总结一下。但是，我们可以用多少种不同的方式从 k 个元素组成金字塔？与 k 的不同分区计数相同的数字（例如，对于 k = 6，我们可以有 (6), (1,5), (2,4), and (1,2,3)）。 Wikipedia and a sequence at OEIS 中描述了为不同分区的计数生成 function/recurrence。

重复，基于Pentagonal number Theorem：

q(k) = ak + q(k − 1) + q(k − 2) − q(k − 5) − q(k − 7) + q(k − 12) + q(k − 15) − q(k − 22)...
  where ak is (−1)^(abs(m)) if k = 3*m^2 − m for some integer m and is 0 otherwise.

(The subtracted coefficients are generalized pentagonal numbers.)

由于 Wikipedia 中描述的循环要求所有前面的 q(n) 的计算得出更大的 q(n)，我们可以简单地对沿途的结果求和以获得我们的结果。

JavaScript代码：

function numPyramids(n){

  var distinctPartitions = [1,1],
      pentagonals = {},
      m = _m = 1,
      pentagonal_m = 2,
      result = 1;

  while (pentagonal_m / 2 <= n){
    pentagonals[pentagonal_m] = Math.abs(_m);
    m++;
    _m = m % 2 == 0 ? -m / 2 : Math.ceil(m / 2);
    pentagonal_m = _m * (3 * _m - 1);
  }

  for (var k=2; k<=n; k++){
    distinctPartitions[k] = pentagonals[k] ? Math.pow(-1,pentagonals[k]) : 0;
    var cs = [1,1,-1,-1],
        c = 0;
    for (var i in pentagonals){
      if (i / 2 > k)
        break;
      distinctPartitions[k] += cs[c]*distinctPartitions[k - i / 2];
      c = c == 3 ? 0 : c + 1;
    }
    result += distinctPartitions[k];
  }
  return result;
}

console.log(numPyramids(6)); // 13

金字塔动态规划

Pyramids dynamic programming

algorithm

dynamic-programming