将 n 个对象划分为 k 个组的方法的数量，以便没有一个组的对象比以前形成的组少？

Question

示例：n=8，k=4 答案：5

[1,1,1,5], [1,1,2,4], [1,1,3,3], [1,2,2,3], [2,2,2,2]

我想过应用动态编程来统计8个对象可以分成4组的方法，但无法理解如何跟踪前一组中的对象数量。

DP方法：

for(int j=0;j<=n;j++)
{
    for(int i=1;i<=k;i++)
    {
        if(j<i)
            continue;
        if(j==i)
            dp[j]=1;
        for(int k=1;k<i;k++)
        {
            dp[j]+=dp[k]*dp[j-k];
        }
    }
}

请帮助提供方法。我对 DP 比较陌生。

Answer 1

这些被称为部件数量受限的分区。递归背后的想法，它等于最大部分是的分区数量k（证明作为一个简短而有趣的阅读）是，如果分区的最小部分是 1，我们已经将 1 添加到所有分区n - 1分成k - 1几部分（保证最小的部分是1）；如果最小的部分不是 1，我们在into部分的k所有分区中的每个部分都加 1 （保证每个部分都大于 1）。n - kk

这是一个简单的记忆：

function f(n, k, memo={}){
  if (k == 0 && n == 0)
    return 1

  if (n <= 0 || k <= 0)
    return 0

  let key = String([n, k]) // Thanks to comment by user633183

  if (memo.hasOwnProperty(key))
    return memo[key]

  return memo[key] = f(n - k, k, memo) + f(n - 1, k - 1, memo)
}

console.time('time taken')
console.log(f(1000, 10))
console.timeEnd('time taken')

下面是自下而上：

function f(n, k){
  let dp = new Array(n + 1)
  for (let i=0; i<n+1; i++)
    dp[i] = new Array(k + 1).fill(0)
  dp[0][0] = 1
  
  for (let i=1; i<=n; i++)
    for (let j=1; j<=Math.min(i, k); j++)
      dp[i][j] = dp[i - j][j] + dp[i - 1][j - 1]

  return dp[n][k]
}

console.time('time taken')
console.log(f(1000, 10))
console.timeEnd('time taken')