我在一次采访中遇到了这个问题而无法理解。我相信它有一个动态的编程解决方案，但它让我望而却步。
给定多个砖块，输出可能的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也是有意义的，因为我们不能在底部行上面有更多的砖块 除 这就是我失去它的地方，我的思绪分崩离析，在某些情况下（少数情况下）你可以I.e. N = 10
X
XX
XXX
XXXX
现在底行有4个，但最左边有6个位于顶部
但是当n = 11时，我们不能有低于n / 2砖的底行。还有另一种奇怪的不一致性，如n = 4，我们不能有一排n / 2 = 2砖。
让我们选择一个合适的定义：
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 只要它是 > 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)
您可以通过多少种方式构建宽度金字塔 ñ？通过放任何宽度的金字塔 n-1个 在层的顶部或更少的地方 ñ 砖块。因此，如果 P（N） 是宽度金字塔的数量 ñ， 然后 p（n）= sum [m = 1到n-1]（p（m）* c（n，m）），哪里 c（n，m） 是可以放置一层宽度的方式的数量 米 在一层宽度上 ñ （我相信你可以自己解决这个问题）。
然而，这并不限制砖的数量。通常，在DP中，必须将任何资源限制建模为单独的维度。所以现在你的问题 p（n，b）：“你可以建造多少金字塔宽度 ñ 总共 b 砖块？？在递归公式中，对于在当前建筑物上方建造较小金字塔的每种可能方式，您需要参考正确数量的剩余砖块。我将其作为挑战，让您计算出递归公式;让我知道你是否需要任何提示。
您可以将您的递归视为：给定 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 版。此外，您可能希望从底行开始并填充金字塔中的上行。
因为我们被要求计算任何基数小于或等于的金字塔 n，我们可以依次考虑每个基数（1个元素的金字塔，2个元素，3 ......等）并总结它们。但是我们可以用多少种不同的方式组成金字塔 k 元素？与不同分区的计数相同的数字 k （例如，为 k = 6， 我们可以有 (6), (1,5), (2,4), and (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