问谷歌面试之谜

EN

这要求您找到将b写为n正整数和的方法的数量。答案是b到n parts中的compositions的个数，即(b-1 choose n-1)。

现在，如果我们考虑到部件的大小限制为a的约束，问题就变得更有趣了。为此，我建议使用generating functions。答案将是乘积(x+x^2+...+x^a)^n中的x^b系数。为什么？因为对于每个骰子(骰子的单数)，您有一个介于1和a之间的数字，这个数字由x的指数表示。当您从每个n术语中提取一个x^i时，这等同于该骰子上出现的数字i。指数的和必须是您要计算的和，即b。

我们甚至可以使用multinomial theorem来简化这个问题，它说明：

(x + x^2 + ... + x^a)^n = sum_{k1+k2+...+ka=n} (n multichoose k1,k2,...,ka) x^{k1+2*k2+...+a*ka}

所有ki >= 0都在那里。所以答案是，方法的数量是

sum_{k1+k2+...+ka=n & k1+2*k2+...+a*ka=b} (n multichoose k1,k2,...,ka)

我将有一个数组hits[max + 1]，它计算每个值的可能组合的数量。max为n * a，当然hits[0] to hits[n - 1]将保持为空。

最愚蠢的方法是执行n for循环(每个骰子一个)，并在hits中为骰子的当前和注册一个命中。

一种不那么愚蠢的方法是使用一些组合学，其中我写出了每个排序的混洗的组合数量：

1111有1个组合(sum = 4)

1112有4个组合(sum = 5)

有4个1113的组合(sum = 6)

..。

1123有4*3/2个组合(sum = 7)

..。

1234有4*3*2个组合(sum = 10)

..。

aaaa (sum = n * a)有1个组合

与愚蠢的解决方案相比，您需要在for循环中花费的时间要少得多。

您可以在每次迭代中获得许多命中，而不是使用dumb方法只命中一次。

这些for循环只是将(n - 1)个分区分隔移动到(1，2，3，4，...，a)上。间隔可以在同一位置(例如，对于case 1111，间隔都在1和2之间)，但间隔不能低于1或高于a。

假设a足够大(具体地说，a>=b-n)，这可以归结为

x1+x2+x3+...+xn=b

这是在n个孩子中分发b糖果的典型问题。如果你想避免零面模具，应该很容易看出

(y1+1)+(y2+1)...+(yn+1)=b
y1+y2+...+yn=b-n

因此，z1+z2+...zk=n的一般解决方案是C(n+k-1，k-1)

收到几票否决后的编辑：

假设我们对'a‘有限制，即b-n>a，我们可以将其表示为DP问题，其中

dp[k][j] is no. of ways to get a sum of j using dices 1 to k inclusive
dp[1][j] is 0 if j>a or j==0 else 1

然后我们就可以有如下的求值关系

from k = 2 to n
  from j = 1 to b
     from x = 1 to a
        dp[k][j] += dp[k-1][j-x] where x is from 1 to a at max and x<j

并且答案应该是dpn，存储if的阶为n*b，运行时间为O(n*b*a)