更新
虽然下面的讨论仍然有用，但 גלעד ברקן的答案提供了一种更好的基础算法，使我们可以跳过我的min参数。(我知道我应该查一下的!) 这种理解可以显著提高下面使用的算法的性能。
将动态规划（DP）视为一种简单的优化技术，可以加速某些递归过程。如果您的递归调用重复（如斐波那契数列），则存储它们的结果可以极大地加快程序的运行速度。但是基本逻辑仍然是递归调用。因此，让我们首先通过递归解决这个问题，看看我们可以在哪里应用DP优化。
即使算法时间是指数级别的，(8,4)只有五个解决方案，因此足够小，可能还是可以处理的。让我们尝试一个简单的递归。起初，让我们实际构建输出而不是计算它，以便进行双重检查，确保我们做得正确。
这个版本是基于这样的想法：我们可以设置列表的第一个数字，将该值作为剩余元素的最小值跟踪，并对剩余位置进行递归。最后，我们使用更高的初始数字再次尝试。因此，除了我们的n和k输入外，我们还需要保留一个min参数，我们从1开始。
以下是一个版本：
const f = (n, k, min = 1) =>
k < 1 || n < k * min
? []
: k == 1
? [[n]]
: [
... f (n - min, k - 1, min) .map (xs => [min, ...xs]),
... f (n, k, min + 1)
]
console .log (
f (8, 4)
)
你没有指定语言标签；如果JavaScript ES6语法不清楚，我们可以用另一种方式重写。
既然看起来正确，我们可以写一个更简单的版本来计算结果:
const f = (n, k, min = 1) =>
k < 1 || n < k * min
? 0
: k == 1
? 1
: f (n - min, k - 1, min) + f (n, k, min + 1)
console .log (
f (8, 4)
)
但如果我们要尝试一个更大的集合，比如f（1000,10）（经过检验，应该是8867456966532531），计算可能需要一些时间。我们的算法可能是指数级的。因此，我们可以采用两种动态规划方法来解决这个问题。最明显的方法是从下往上的方法：
const f = (_n, _k, _min = 1) => {
const cache = {}
for (let n = 1; n <= _n; n ++) {
for (let k = 1; k <= Math.min(_k, n); k++) {
for (let min = n; min >= 0; min--) {
cache [n] = cache[n] || {}
cache [n] [k] = cache [n] [k] || {}
cache [n] [k] [min] =
k < 1 || n < k * min
? 0
: k == 1
? 1
: cache [n - min] [k - 1] [min] + cache [n] [k] [min + 1]
}
}
}
return cache [_n] [_k] [_min]
}
console.time('time taken')
console .log (
f (1000, 10)
)
console.timeEnd('time taken')
这里确定正确的边界很棘手，如果没有其他原因，因为递归基于
min值的增加。很可能我们在计算中得到了不需要的东西。
这也是丑陋的代码，失去了原始代码的优雅和可读性，只获得了性能。
我们仍然可以通过记忆化函数来保持优雅，这是一种自上而下的方法。通过使用可重用的
memoize函数，我们几乎可以完整地使用我们的递归解决方案：
const memoize = (makeKey, fn) => {
const cache = {}
return (...args) => {
const key = makeKey(...args)
return cache[key] || (cache[key] = fn(...args))
}
}
const makeKey = (n, k, min) => `${n}-${k}-${min}`
const f = memoize(makeKey, (n, k, min = 1) =>
k < 1 || n < k * min
? 0
: k == 1
? 1
: f (n - min, k - 1, min) + f (n, k, min + 1)
)
console.time('time taken')
console .log (
f (1000, 10)
)
console.timeEnd('time taken')
memoize 将一个每次调用都计算其结果的函数转换为仅在第一次看到某个特定输入集时计算它们的函数。这个版本需要您提供另一个将参数转换成唯一键的函数。还有其他写法，但它们有点丑陋。在这里，我们只是将 (8, 4, 1) 转换为 "8-4-1"，然后在该键下存储结果。没有歧义。下一次使用 (8, 4, 1) 调用时，已经计算出的结果将立即从缓存中返回。
请注意，有一种诱惑尝试...
const f = (...args) => {...}
const g = memoize(createKey, f)
但是，如果函数
f 中的递归调用指向
f 本身，则此方法无法正常工作。如果它们指向
g，则我们已经混淆了实现，
f 不再是独立的，因此几乎没有理由这样做。因此，我们将其编写为
memomize(createKey, (...args) => {...})。高级技术
提供替代方案 超出了本文讨论的范围。
决定使用自底向上的DP还是自顶向下的DP是一个复杂的问题。从上面的案例中可以看出，对于给定的输入，自底向上版本运行得更快。额外的函数调用会产生一些递归开销，并且在某些情况下可能会受到递归深度限制的影响。但是，自顶向下的技术有时完全可以通过仅计算所需内容来抵消这一点。自底向上将计算所有较小的输入（对于“较小”的某种定义），以便找到您的值。自顶向下只会计算解决您的问题所必需的那些值。
1 玩笑！我只有在使用动态规划后才发现了价值。
[n, k]进行一次字符串化来显著减少memo示例中的运行时间 - 即，const key = \${n},${k}`，然后使用memo.hasOwnProperty(key)、memo[key]和memo[key] = ...。你也可以使用const key = String([n, k])`，但实际上没有必要分配数组。 - Mulani和j对应于上面递归公式中的n和k。 - גלעד ברקן