您的问题可以转置，因此您的缓存中只需要 3 个键，并且启动的运行时间要少得多。更少的不同键意味着更好的缓存（比我更聪明的人可能仍然会找到更便宜的解决方案）。
让我们将分区视为集合。每组的元素应按顺序排列（升序）。sum := 15, k := 4, m:= 10当您陈述as的预期结果时，您已经隐含地做到了这一点[1, 2, 3, 9]; [1, 2, 4, 8] ...。
您为分区定义的限制是：
k每组的确切元素- 最大值
m作为元素
- 不同的价值观
- 非零正整数
区分的限制其实有点麻烦，我们就解除吧。为此，我们需要稍微改变一下问题。因为你的集合中的元素是升序的（并且不同的），我们知道，每个元素的最小值是一个升序序列（如果我们忽略总和必须是sum），所以 minia 是：[1, 2, 3, ...]。例如，如果m小于k，则可能的分区数将始终为零。同样，如果总和[1, 2, 3, ... k]大于sum，则结果也为零。我们在一开始就排除了这些边缘情况，以确保转换是合法的。
让我们看一下“法律分区”的几何表示以及我们希望如何对其进行转换。我们将k列、m行和sum正方形填充为蓝色（浅蓝色或深蓝色）。
红色和深蓝色方块无关紧要，正如我们已经知道的，深蓝色方块必须始终填充，而红色方块必须始终为空。因此，我们可以将它们排除在我们的计算之外，并在我们进行时假设它们各自的状态。生成的框显示在右侧。每列都被它的位置“向下移动”，红色和深蓝色区域被切断。我们现在有一个较小的整体框，一列现在可以是空的（相邻列之间可能有相同数量的蓝色框）。
从算法上讲，转换现在的工作方式如下：对于合法分区中的每个元素，我们减去它的位置（从 1 开始）。所以对于
[1, 2, 4, 8]我们得到[0, 0, 1, 4]. 此外，我们必须相应地调整我们的界限 (sum和m)：
// from the sum, we subtract the sum of [1, 2, 3, ... k], which is (k * (k + 1) / 2)
sum_2 = sum - (k * (k + 1) / 2)
// from m we subtract the maximum position (which is k)
m_2 = m - k
现在我们已经将我们的分区问题转换为另一个分区问题，一个没有不同元素限制的分区问题！此外，这个分区可以包含 element 0，而我们原来的不能。（我们保持内部升序）。
现在我们需要稍微改进一下递归。如果我们知道元素是升序的，不一定是不同的并且总是不等于m_2，那么我们已经将可能的元素绑定到一个范围内。例子：
[0, 1, 3, n1, n2]
=> 3 <= n1 <= m_2
=> 3 <= n2 <= m_2
因为我们知道n1并且n2在示例中是3或更大，当调用递归时，我们也可以将它们同时归约3和归约sum_2（2 * 3一个是'open'元素的数量，一个是最后一个'fixed'元素的值）。这样，我们在递归中传递的内容没有上限和下限，而只有一个上限，这就是我们之前的 ( m) 。
正因为如此，我们可以抛出 1 个缓存键值：start。相反，在解决这个简化的问题时sum，我们现在只有 3:m和, 。k
以下实现适用于此效果：
@Test
public void test() {
calcNumRIPdistinctElementsSpecificKmaxM(600, (short) 25, (short) 200);
}
public BigInteger calcNumRIPdistinctElementsSpecificKmaxM(int sum, short k, short m) {
// If the biggest allowed number in a partition is less than the number of parts, then
// they cannot all be distinct, therefore we have zero results.
if (m < k) {
return BigInteger.ZERO;
}
// If the sum of minimum element-values for k is less than the expected sum, then
// we also have no results.
final int v = ((k * ((int) k + 1)) / 2);
if (sum < v) {
return BigInteger.ZERO;
}
// We normalize the problem by lifting the distinction restriction.
final Cache cache = new Cache();
final int sumNorm = sum - v;
final short mNorm = (short) (m - k);
BigInteger result = calcNumRIPspecificKmaxM(sumNorm, k, mNorm, cache);
System.out.println("Calculation (n=" + sum + ", k=" + k + ", m=" + m + ")");
System.out.println("p = " + result);
System.out.println("entries = " + cache.getNumEntries());
System.out.println("c-rate = " + cache.getCacheRate());
return result;
}
public BigInteger calcNumRIPspecificKmaxM(int sum, short k, short m, Cache cache) {
// We can improve cache use by standing the k*m-rectangle upright (k being the 'bottom').
if (k > m) {
final short c = k;
k = m;
m = c;
}
// If the result is trivial, we just calculate it. This is true for k < 3
if (k < 3) {
if (k == 0) {
return sum == 0 ? BigInteger.ONE : BigInteger.ZERO;
} else if (k == 1) {
return sum <= m ? BigInteger.ONE : BigInteger.ZERO;
} else {
final int upper = Math.min(sum, m);
final int lower = sum - upper;
if (upper < lower) {
return BigInteger.ZERO;
}
final int difference = upper - lower;
final int numSubParts = difference / 2 + 1;
return BigInteger.valueOf(numSubParts);
}
}
// If k * m / 2 < sum, we can 'invert' the sub problem to reduce the number of keys further.
sum = Math.min(sum, k * m - sum);
// If the sum is less than m and maybe even k, we can reduce the box. This improves the cache size even further.
if (sum < m) {
m = (short) sum;
if (sum < k) {
k = (short) sum;
if (k < 3) {
return calcNumRIPspecificKmaxM(sum, k, m, cache);
}
}
}
// If the result is non-trivial, we check the cache or delegate.
final Triple<Short, Short, Integer> key = Triple.of(k, m, sum);
final BigInteger cachedResult = cache.lookUp(key);
if (cachedResult != null) {
return cachedResult;
}
BigInteger current = BigInteger.ZERO;
// i = m is reached in case the result is an ascending stair e.g. [1, 2, 3, 4]
for (int i = 0; i <= m; ++i) {
final int currentSum = sum - (i * k);
if (currentSum < 0) {
break;
}
short currentK = (short) (k - 1);
short currentM = (short) (m - i);
current = current.add(calcNumRIPspecificKmaxM(currentSum, currentK, currentM, cache));
}
// We cache this new result and return it.
cache.enter(key, current);
return current;
}
public static class Cache {
private final HashMap<Triple<Short, Short, Integer>, BigInteger> map = new HashMap<>(1024);
private long numLookUps = 0;
private long numReuse = 0;
public BigInteger lookUp(Triple<Short, Short, Integer> key) {
++numLookUps;
BigInteger value = map.get(key);
if (value != null) {
++numReuse;
}
return value;
}
public void enter(Triple<Short, Short, Integer> key, BigInteger value) {
map.put(key, value);
}
public double getCacheRate() {
return (double) numReuse / map.size();
}
public int getNumEntries() {
return map.size();
}
public long numLookUps() {
return numLookUps;
}
public long getNumReuse() {
return numReuse;
}
}
注意：我在这里使用了 apache-common 的Triple-class 作为键，以节省显式键类的实现，但这不是运行时的优化，它只是节省了代码。
编辑：除了修复@MBo 发现的问题（谢谢），我添加了一些快捷方式来达到相同的结果。该算法现在性能更好，缓存（重用）率更高。也许这会满足您的要求？
优化解释（它们仅适用于上述问题的转置之后）：
- 如果
k > m，我们可以垂直“翻转”矩形，并且对于合法分区的数量仍然得到相同的结果。这会将一些“躺”配置映射到“直立”配置，并减少不同键的总量。
- 如果矩形中正方形的数量大于“空格”的数量，我们可以将“空格”视为正方形，这会将另一组键映射在一起。
- 如果
sum < k和/或sum < m，我们可以减少k和/或m求和，并且仍然得到相同数量的分区。（这是影响最大的优化，因为它经常跳过多个冗余的中间步骤并经常达到m = k = sum）
