Number of ways to divide n objects in k groups, such that no group will have fewer objects than previously formed groups?

Question

Example: n=8, k=4 Answer: 5

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

I thought of applying dynamic programming to count the number of ways 8 objects can be divided into 4 groups, but can't understand how to keep track of the number of objects in the previous group.

DP approach:

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];
        }
    }
}

Please help with the approach. I'm relatively new to DP.

Answer 1

These are known as partitions with restricted number of parts. The idea behind the recurrence, which is equal to the number of partitions whose largest part is k (proof is left as a short, interesting read) is that if the smallest part of the partition is 1, we've added 1 to all partitions of n - 1 into k - 1 parts (to guarantee the smallest part is 1); and if the smallest part is not 1, we've added 1 to each of k parts in all partitions of n - k into k parts (guaranteeing that each part is greater than 1).

Here's a straightforward memoization:

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

Here's bottom-up:

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