Partition a array into k subarrays

#1

can u tell me how to partion a given array into k subsrrays under many diff given condition like sum of all subarrays are equal or diff of max sum subarray and min sum subarray maximize/minimise etc etc…

#2

hello @Ashu1318
it will depend on question.

but if u want to compute something then u can use dp

dp[i][j]-> answer when u break {0…i} in k subarrays

and to compute dp[i][j] what u need to do is u just have to pick one subarray say u pick [l…i].
then
dp[i][j]= answer for picked subarray + answer for dp[l-1][j-1]

#3
#4

i’m applying that approch but got stuck can u plz see my code and try to figer out errors or fix prob

#5
#6

correct ur recurrence relation.

it should be
solve(i,k)= made one partition at j so answer of portion [i…j] (this is in one stable) + solve(j+1,k-1)

check this and let me know if any thing is not clear

int solve(int i ,int k,string &s,vector<vector<int> > &dp)
{
    if(i==s.size()){
        if(k!=0)
        return INT_MAX;
        
        return 0;
    }
    if(k==0)
    return INT_MAX;
    
    if(dp[i][k]!=-1)
     return dp[i][k];
     
     int ans=INT_MAX;
     int w=0,b=0;
     
     for(int j=i;j<s.size();j++){
         if(s[j]=='W')
           w++;
           else
           b++;
         int ans1=solve(j+1,k-1,s,dp);
         if(ans1!=INT_MAX){
          ans=min(ans,w*b+ans1);// here w*b is answer of portion [i...j] and ans1 is answer of solve(j+1,k-1)
        // cout<<ans1<<" "<<j+1<<"  "<<k-1<<" "<<w<<" "<<b<<" , ";
             
         }
     }
     
     dp[i][k]=ans;
     return dp[i][k];
    
    
}
int Solution::arrange(string A, int B) {
    if(A.size()<B)
    return -1;
    vector< vector<int> > dp(A.size()+1,vector<int>(B+1,-1) );
    return solve(0,B,A,dp);
    
    
}