金字塔动态编程

Question

我在一次采访中遇到了这个问题而无法理解.我相信它有一个动态的编程解决方案,但它让我望而却步.

给定一些砖块,输出可能的2d金字塔总数,其中金字塔被定义为任何结构,其中一排砖块的砖块严重少于其下方的砖块.你不必使用所有砖块.

砖块只是一个正方形,连续砖块的数量是唯一重要的信息.

真的坚持这个,我认为很容易解决每个问题1 ... n迭代和总和.但是提出金字塔的数量可能与我的砖块正在躲避我.

例如,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

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

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砖块。而且，i <= m - 1根据 的定义m。

这导致递归表达式：

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

您可以f递归计算，但使用动态编程当然会更快。不过，存储结果矩阵很简单，因此我将其留给您。

回到您正在寻找的答案的原始声明，只要是 ，f(N, N+1)-1选择哪个值并不重要。基于递归公式，很容易证明对于每个：m> Nf(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)