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