递归算法
计算一个整数的所有分区n with m部分，递归算法是显而易见的选择。对于本案n, m，算法贯穿每个选项k = 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+4 and 4+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.
最小值为 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 = 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, k被替换为n - 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+3, 3+3+4 and 5+5+6全部被其规范形式所取代1+1+2，并且更频繁地重复较小的中间计算集。
记忆化
当使用递归算法进行分区时，许多计算会重复多次。随着 n 和 m 值的增加，递归次数很快变得巨大；例如破案150, 23（如下图所示），案例4, 2计算了23,703,672次。
但是，唯一计算的数量永远不能大于n * m。因此通过将每次计算的结果缓存在一个n*m大小的数组中，不超过n * m需要进行计算；计算一次案例后，算法可以使用存储的值。这极大地提高了算法的效率；例如如果没有记忆，需要 422,910,232 次递归才能解决这个问题150, 23;通过记忆，只需要 15,163 次递归。
下图显示了这种情况下的缓存读取和写入。灰色单元未被使用，白色单元被写入但从未被读取。总共有 2042 次写入和 12697 次读取。
减少缓存大小
您会注意到左上角和右下角的三角形从未使用过； m的值越接近n，未使用的区域就越大。为了避免这种空间浪费，可以通过存储以下值来将这两个三角形之间的平行四边形倾斜 45°n, m in n - m, m。缓存大小因此减少(n - 1) * (m - 1) to (n - m) * (m - 1)，以及最坏的情况n,m <= 150不再是149 * 149 = 22201，而是75 * 74 = 5550，小于25%的大小。
代码示例 1：无记忆
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)
代码示例 2：带记忆功能的快速版本
这个版本缓存了中间结果，比基本算法快得多。即使这个 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
(The worst case for n = 1000, which is m = 81, solves to 4.01779428811641e+29, and this result is also returned nearly instantly. Because it exceeds Javascript's maximum safe integer of 253-1, this is of course not an exact result.)
代码示例 3：具有记忆功能和较小缓存的快速版本
此版本使用倾斜的缓存索引来减少内存需求。
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
