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

Test case:

n=8, k=4

output: 5

Explanation:

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

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

Test case:

n=8, k=4

output: 5

Explanation:

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

1 Like

as in the question n<=200 3 state dp solution easily work for me.

if anyone solved with better time complexity plz inform.

```
'''
```

ll dp[205][205][205];//n k prev

ll solve(int n,int k,int prev)

{

if(n==0&&k==0)

return 1;

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

return 0;

if(dp[n][k][prev]!=-1)

return dp[n][k][prev];

ll ans=0;

for(int i=prev;i<=n;i++)

ans+=solve(n-i,k-1,i);

return dp[n][k][prev]=ans;

}

```
int main()
{
//FAST;
int n;
cin>>n;
int k;
cin>>k;
memset(dp,-1,sizeof(dp));
ll ans=0;
for(int i=1;i<=n;i++)
ans+=solve(n-i,k-1,i);
cout<<ans;
}
```