0 like 0 dislike
747 views
| 747 views

0 like 0 dislike

Lets create our dynamic-programming , dp[i][j] which indicates the number of ways to divide an array of size 'i' into 'j' distinct parts ..

What can be the recurrence relation ?

dp[i][j] = (dp[i-1][j-1]  + dp[i-2][j-1] + ......... and so on..till dp[j-1][j-1])

Basically , to calculate the best answer for index 'i' ,  we select a block of size '1' at index 'i' and calculate the number of ways possible to make j-1 parts as the last block will make total 'j' parts.. , which will be dp[i-1][j-1].

Similarly, we try to make last block of size '2' , then size '3' , then size '4' , then size '5' , ... and so on....

So it adds up ..... //RAM__rAM!!!

Code C++ :

```#include <bits/stdc++.h>
using namespace std ;
int dp[100+5][5+10];
int main()
{
int n,k;
cin>>n>>k;
int j = 1;
while(j<=n)
{
dp[j] = 1 ;
j++;
}
int p = 2 ;
while(p<=k)
{
//dp[i][p] ==== dp[i-1][p-1] + dp[i-2][p-1] + dp[p-1]..........
int i = p;
while(i<=n)
{

int j = i-1;
int sum = 0 ;
while(j>=1)
{
sum = sum + dp[j][p-1];
j--;
}
dp[i][p] = sum  ;
i++;
}
p++;
}
cout<<dp[n][k] ;
return 0 ;
}```
by Expert (19,120 points)