来自 MS f2f 面试的面试问题：
确定积分解的个数
x1 + x2 + x3 + x4 + x5 = N
在哪里0 <= xi <= N
所以基本上我们需要在最多 5 个部分中找到 N 的分区数 假设用纸和铅笔来解决。虽然没有取得太大进展，有人对此有解决方案吗？
问问题
272 次
5 回答
3
假设数字严格 > 0。
考虑一个整数段[0, N]。问题是将它分成4个正长度的段。想象一下，我们通过在相邻数字之间放置 4 个分隔点来做到这一点。有多少种方法可以做到这一点？C(N-1, 4)。
现在，一些数字可以是 0-s。让k是非零数字的数量。我们可以以C(5,k)种方式选择它们，每种方式都有C(N-1,k)种分裂。将[0,5]范围内的所有k累加，我们得到Sum[ C(5,k) * C(n-1,k); k = 0 到 5]
于 2012-08-07T12:34:51.577 回答
2
@Grigor Gevorgyan 确实提供了找出解决方案的正确方法。
想想什么时候
1 <= xi
这正好将 N 个点分成 5 段。它相当于在 N-1 个可能的位置（相邻数字之间）中插入 4 个“分割点”。所以答案是 C(N-1,4)
那么什么时候
0 <= xi
?
如果你有 X+5 个点的解
1 <= xi
谁的答案是C(N-1,4)=C(X+5-1,4)=C(X+4,4)
然后你只需从每组中删除一个点，你就有了 X 个点的解，
0 <= xi
这意味着，现在的答案完全等于C(X+4,4)
于 2012-08-07T13:04:52.170 回答
2
寻找“结合重复”部分：具体案例在该部分下用图解说明进行说明。（一张图值得几句话！）
于 2012-08-07T13:10:28.467 回答
2
于 2012-08-07T13:12:36.577 回答
1
如果要求笔和纸解决方案，则组合解决方案更合适。这也是经典的解决方案。这是一个动态编程解决方案。
让dp[i, N] = number of solutions of x1 + x2 + ... +xi = N.
让我们来看看x1 + x2 = N：
我们有解决方案：
0 + N = N
1 + N - 1 = N
...
N + 0 = N
所以dp[2, N] = N + 1解决方案。
让我们来看看x1 + x2 + x3 = N：
我们有解决方案：
0 + (0 + N) = N
0 + (1 + N - 1) = N
...
0 + (N + 0) = N
...
N + 1请注意，到目前为止有一些解决方案。继续：
1 + (0 + N - 1) = N
1 + (1 + N - 2) = N
...
1 + (N - 1 + 0) = N
...
请注意，还有另一种N解决方案。继续：
...
N - 1 + (0 + 1) = N
N - 1 + (1 + 0) = N
=> +2 solutions
N + (0 + 0) = N
=> +1 solution
所以我们有dp[3, N] = dp[2, N] + dp[2, N - 1] + dp[2, N - 2] + ... + dp[2, 0].
还要注意dp[k, 0] = 1
由于矩阵的每一行都需要N求和，因此计算的复杂度dp[k, N]是O(k*N)，这与组合数学解决方案所需的一样多。
为了保持每一行的复杂性O(N)，存储s[i] = sum of the first i elements on the previous row. 使用的内存也可以减少到O(N).
于 2012-08-07T13:20:26.390 回答