金字塔动态规划

Question

金字塔动态规划

algorithmdynamic-programming

11

我在一次面试中遇到了这个问题，但是无法解决。我相信它有一个动态规划的解决方案，但我还没有想出来。

给定一定数量的砖块，输出可能的二维金字塔总数，其中金字塔定义为任何一行砖块比下面一行少的结构。您不必使用所有砖块。

砖块只是一个正方形，每一行中的砖块数量是唯一重要的信息。

对于这个问题真的很困惑，我认为通过逐步解决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宽度的底部行，因为顶部不能比底部拥有更多的积木，但在某些情况下（极少数情况），可以实现这点，例如N = 10。

X
XX
XXX
XXXX

现在底部一行有4块砖，但是还有6块要放在上面。

但是当n = 11时，我们不能让底部一行少于n/2块砖。对于n = 4也存在类似的奇怪不一致情况，即我们不能让底部一行只有n/2 = 2块砖。

- shane

如果您不必使用所有的积木，使用0个积木也可以吗？那么，为什么不为n = 6使用14个合法的金字塔呢？ - John Coleman

不确定，我记得那个问题陈述不太清楚，但我认为最好将金字塔的定义限制为至少一个砖块。我没在问题陈述中提到这一点是个聪明的决定。 - shane

听起来递归函数非常适合。对于任何组合/排列问题，我首先考虑递归而不是动态规划。 - slebetman

你的陈述“一旦你考虑了第一行，找出你可以在其上建造多少金字塔”是一个递归语句。 - slebetman

1

记忆化是一种优化技术。在算法设计阶段不必考虑它。 - slebetman

显示剩余4条评论

4个回答

3

你可以用多少种方法建造宽度为n的金字塔？将任何宽度为n-1或更小的金字塔放在n块砖的顶部即可。所以如果p(n)是宽度为n的金字塔数量，则p(n)=sum [m=1 to n-1](p(m)*c(n,m))，其中c(n,m)是将宽度为m的一层放在宽度为n的一层上的方式数（相信你自己能解决这个问题）。

然而，这不会限制砖块的数量。通常，在动态规划中，任何资源限制都必须建模为单独的维度。因此，您现在的问题是p(n,b):“您可以用总共b块砖建造宽度为n的金字塔有多少种方法”？在递归公式中，对于每种更小的金字塔建造方式，您需要引用正确数量的剩余砖块。我留给你作为一个挑战去解决递归公式；如果你需要任何提示，请告诉我。

- Aasmund Eldhuset

我没有考虑宽度（底行）作为一个维度。我只是在考虑使用n个砖块来穷尽地创建一些金字塔。例如，如果n = 3，对于i = 1，我们有一个孤立的砖块作为金字塔，对于i = 2，我们有一排2个砖块，对于i = 3，我们有(3)和(2,1)。当依赖于砖块数量时，宽度可能会发生变化，那么我该如何使用宽度作为限制条件呢？ - shane

我相当有信心地认为，使用所有的 n 个砖头，我们可以在底部行使用介于 n 和 n/2 个砖头之间的 k 个砖头，尽管我不确定如何证明它。然后对于每一个这样的情况，我们加上一个 + 使用 n-k 个砖头在其顶部堆叠所能建造的金字塔数量。正确的轨迹？ - shane

@shane：我忘了提到这一点，但确实需要尝试所有可能的底层宽度，看看哪一个能给出最高的结果。 - Aasmund Eldhuset

如果我在递归中省略宽度，那么我就可以接近 p(b) = sum(0 <= k < b/2, p(b - k) + 1) 。这里我基本上遍历了所有至少为 b/2 的底面，并将其加到我可以放在其上方的较小金字塔的数量中。但是当 b = 4 而不是 b = 6 时会发生奇怪的事情，在 4 中我不能有一个 b/2=2 的基座，但在 6 中我可以有一个底面为 3 的基座。我不确定这是否是一个异常情况，一切超过 4 的数字是否有效，或者这些数字是否具有我不知道的某些属性。 - shane

@shane：你不能忽略宽度，因为你需要知道下一级的宽度限制。例如：对于_n=6_，可以从基础宽度3开始，对于_n=7_，可以从基础宽度4开始，在这两种情况下，你都会问自己在剩下的 n=3 块砖的情况下能建造什么。然而，只有当你正在建造的层包含至少4个块时，将所有3个砖块放在同一层中才是一个选项。 - Aasmund Eldhuset

2

鉴于我们被要求计算不大于n的任何基数的金字塔，我们可以逐个考虑每个基数（1个元素的金字塔，2个元素的金字塔，3个元素...等等）并将它们相加。但是，我们可以用多少种不同的方式从k个元素中组成一个金字塔呢？与不同分区k的数量相同（例如，对于k = 6，我们可以有(6)、(1,5)、(2,4)和(1,2,3)）。关于不同分区数量的生成函数/递归在维基百科和序列OEIS中有描述。

递推公式，基于五边形数定理：

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.)

由于维基百科中描述的循环需要计算所有先前的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

- גלעד ברקן

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;
}

我会让你来实现记忆化或自底向上的动态规划版本。你也可以从金字塔的底部开始，填充上方的行。

- xashru

你能解释一下你选择的范围吗？ - shane

由于在上一行使用了最后一组砖块，因此必须在该行上至少使用 last+1 组砖块（因为我们是从上到下进行的），并且你最多可以在该行上使用 left 组砖块，因为这是你剩余的所有砖块。 - xashru

删除了我的评论，没有意识到我们是从上到下的。 - shane

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Vincent van der Weele · Accepted Answer

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

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就可以了。根据递推公式，很容易证明对于每个k >= 1，都有 f(N, N + 1) = f(N, N + k)：

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)