algorithm - 将 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

这些被称为 partitions with restricted number of parts .递归背后的思想，等于最大部分为k的分区数(证明留作简短而有趣的阅读)是，如果分区的最小部分是 1，我们已将 1 添加到 n - 1 的所有分区中。进入 k - 1零件(保证最小零件为1)；如果最小的部分不是 1，我们就给 k 的每一个加 1 n - k的所有分区中的部分进入 k部分(保证每个部分都大于 1)。

这是一个简单的内存:

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')