2

给定n个骰子，每边'a'和一个总和b，返回可以获得总和b的方式的数量。如何降低时间复杂度和空间复杂度？这是在谷歌采访中被问到的，我不确定答案。

4

3 回答 3

7

这要求你找出写成正整数b和的方法的数量。n答案是组成部分b的数量n，即(b-1 choose n-1)。

现在，如果我们考虑到零件大小限制为 的约束，a问题就会变得更加有趣。我建议为此使用生成函数。答案将是x^b乘积中的系数(x+x^2+...+x^a)^n。为什么？因为对于每个骰子（骰子的单数），在1和之间都有一个数字a，这由 的指数表示x。当您x^i从每个n术语中取一个时，这相当于i该骰子上出现的数字。指数的总和必须是您所追求的总和，即b。

我们甚至可以使用多项式定理稍微简化问题，该定理指出：

(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)
于 2011-12-21T04:55:18.357 回答
0

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

愚蠢的方法是进行nfor循环（每个骰子一个）并hits为当前骰子总和注册一个命中。

不那么愚蠢的方法是使用一些组合，我写出每个有序shuffle 的组合数量：

1111 有 1 种组合（总和 = 4）
1112 有 4 种组合（总和 = 5）
1113 有 4 种组合（总和 = 6）
...
1123 有 4 * 3 / 2 种组合（总和 = 7 )
...
1234 (sum = 10) 有 4 * 3 * 2 个组合
... ( sum = )
有 1 个组合aaaan * a

与愚蠢的解决方案相比，您在 for 循环中花费的时间要少得多。
每次迭代都会获得很多点击，而不是使用哑方法只获得一次点击。

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

于 2011-12-21T16:40:50.127 回答
-2

假设 a 足够大（具体来说是 a>=bn），这归结为

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

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

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

所以 z1+z2+...zk=n 的一般解是 C(n+k-1,k-1)

在收到几个反对票后进行编辑：

假设我们对“a”有限制，即 bn>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

并且答案应该是 dp[n][b] 存储 if 的顺序为 n*b 和运行时间 O(n*b*a)

于 2011-12-21T04:45:32.200 回答