我必须创建一个方法，该方法采用两个整数，让它们成为 and ，并返回有多少种方法可以求和正数来获得。例如，像这样的方法调用应返回 3，因为有 3 种方式可能。它们是 、 和 。顺便说一句，与 相同，因此该方法不应将它们计为两个不同的变体。有人知道问题的解决方案吗？nmmnpartition(6, 2)5 + 14 + 23 + 34 + 22 + 4
已更新：并且不大于 150。nm
要使用部分对整数的所有分区进行计数，递归算法是显而易见的选择。对于这种情况，该算法会遍历第一部分的每个选项，并且对于这些选项中的每一个，它都以大小写的形式递归。例如：nmn, mk = 1, 2, 3...n - k, m - 1
n = 16, m = 4
first part = 1 => recurse with n = 15, m = 3
first part = 2 => recurse with n = 14, m = 3
first part = 3 => recurse with n = 13, m = 3
etc...
经过多次递归后，到达该点的位置 ;那么解决方案是：m = 2
first part = 1 => second part = n - 1
first part = 2 => second part = n - 2
first part = 3 => second part = n - 3
etc...
因此，解决方案的数量等于第一部分的选项数量。m = 2
要仅计数唯一解并丢弃重复项，以便不同时计数，则仅考虑零件形成非递减序列的解;例如：2+44+2
n = 9, m = 3
partitions: 1+1+7 1+2+6 1+3+5 1+4+4
2+2+5 2+3+4
3+3+3
在上升序列中，第一部分的值永远不能大于 。n / m
为了保持上升序列，每个递归都必须使用前一个部分的值作为其部分的最小值;例如：
n = 9, m = 3
k = 1 => recurse with n = 8, m = 2, k >= 1 => 1+7 2+6 3+5 4+4
k = 2 => recurse with n = 7, m = 2, k >= 2 => 2+5 3+4
k = 3 => recurse with n = 6, m = 2, k >= 3 => 3+3
为了避免每次递归都传递最小值，每个递归都替换为 ，它具有相同数量的解。例如：n - k, m - 1, kn - k - (m - 1) * (k - 1), m - 1, 1
n = 9, m = 3
k = 1 => recurse with n = 8, m = 2, k >= 1 => 1+7 2+6 3+5 4+4
k = 2 => recurse with n = 5, m = 2, k >= 1 => 1+4 2+3
k = 3 => recurse with n = 2, m = 2, k >= 1 => 1+1
这不仅简化了代码，还有助于提高使用记忆化的效率，因为像 这样的序列都被它们的规范形式所取代，并且更频繁地重复一组较小的中间计算。2+2+33+3+45+5+61+1+2
使用递归算法进行分区时，许多计算重复多次。随着n和m值的增加，递归的数量很快就会变得巨大;例如，为了解决案例（如下图所示），案例计算了23，703，672次。150, 234, 2
但是，唯一计算的数目永远不能大于 。因此，通过在n * m大小的数组中缓存每个计算的结果，只需要执行计算即可;在计算了一次事例后，算法可以使用存储的值。这大大提高了算法的效率;例如，在没有记忆的情况下，需要422，910，232个递归来解决这种情况;使用记忆，只需要15，163个递归。n * mn * m150, 23
下图显示了这种情况的缓存读取和写入。灰色单元格未使用，白色单元格被写入但从不读取。总共有 2042 次写入和 12697 次读取。
您会注意到左上角和右下角的三角形从未使用过;m 的值越接近 n，未使用的区域就越大。为了避免这种空间浪费，通过将 的值存储在 中，这两个三角形之间的平行四边形可以倾斜 45°。因此，缓存大小从 减少到 ，最坏的情况不再是 149 * 149 = 22201，而是 75 * 74 = 5550，小于大小的 25%。n, mn - m, m(n - 1) * (m - 1)(n - m) * (m - 1)n,m <= 150
function partition(n, m) {
if (m < 2) return m;
if (n < m) return 0;
if (n <= m + 1) return 1;
var max = Math.floor(n / m);
if (m == 2) return max;
var count = 0;
for (; max--; n -= m) count += partition(n - 1, m - 1);
return count;
}
document.write(partition(6, 1) + "<br>"); // 1
document.write(partition(6, 2) + "<br>"); // 3
document.write(partition(9, 3) + "<br>"); // 7
document.write(partition(16, 4) + "<br>"); // 34
document.write(partition(150, 75) + "<br>"); // 8,118,264
// document.write(partition(150, 23)); // 1,901,740,434 (maximum for 150, takes > 10s)此版本缓存中间结果，比基本算法快得多。即使是这个Javascript实现也可以在不到一毫秒的时间内解决n = 150的最坏情况。
function partition(n, m) {
if (m < 2) return m;
if (n < m) return 0;
var memo = [];
for (var i = 0; i < n - 1; i++) memo[i] = [];
return p(n, m);
function p(n, m) {
if (n <= m + 1) return 1;
if (memo[n - 2][m - 2]) return memo[n - 2][m - 2];
var max = Math.floor(n / m);
if (m == 2) return max;
var count = 0;
for (; max--; n -= m) count += (memo[n - 3][m - 3] = p(n - 1, m - 1));
return count;
}
}
document.write(partition(150, 23) + "<br>"); // 1,901,740,434
// document.write(partition(1000, 81)); // 4.01779428811641e+29（n = 1000 的最坏情况是 m = 81，求解为 4.01779428811641e+29，此结果也几乎立即返回。因为它超过了Javascript的最大安全整数253-1，这当然不是一个确切的结果。
此版本使用倾斜的缓存索引来降低内存要求。
function partition(n, m) {
if (m < 2) return m;
if (n < m) return 0;
var memo = [];
for (var i = 0; i <= n - m; i++) memo[i] = [];
return p(n, m);
function p(n, m) {
if (n <= m + 1) return 1;
if (memo[n - m][m - 2]) return memo[n - m][m - 2];
var max = Math.floor(n / m);
if (m == 2) return max;
var count = 0;
for (; max--; n -= m) count += (memo[n - m][m - 3] = p(n - 1, m - 1));
return count;
}
}
document.write(partition(150, 23) + "<br>"); // 1,901,740,434
document.write(partition(150, 75) + "<br>"); // 8,118,264
document.write(partition(150, 127) + "<br>"); // 1255您可以使用动态规划。设为非递减正数的分区数，使得总和为 ，最后一个是 。然后，您可以轻松地看到更新步骤将是：f[n][m][k]mnk
f[n][m][k] → f[n+l][m+1][l] for every l≥ k
要得到 ，表示与最后一个数字无关的所有分区的数量，最后只需对全部求和即可。复杂性将是 .f[n][m]kO(n^2 m)
