Question

How many number of ways are there to split an array into k distinct parts?

Answer 1

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] = 1 ; 
        j++;
    }
    int p = 2 ; 
    while(p<=k)
    {
        //dp[i][p] ==== dp[i-1][p-1] + dp[i-2][p-1] + dp[0][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 ; 
}