Doubt in approach


#1
  1. If we can calculate min cost or each person independently as per the given approach then why are we filling min cost dp table for all the friends in one go by taking the max capacity among friend and that is surely not independent.
  2. I thought of taking the capacity of each friend independently and finding the min cost for each friend but got TLE.

Can anyone help me with the editorial approach/code to make it more clear?

Here is my Code ::

> int Solution::solve(const vector<int> &A, const vector<int> &B, const vector<int> &C) {
>     int ans = 0 ;
>     for(int k = 0 ; k < A.size() ; k++)
>     {   
>         int n = B.size() ;
>         int m = A[k] ;
>         vector<vector<int> > dp(n+1 , vector<int> (m+1, -1)) ;
>         for(int i = 0 ; i <= n ; i++)
>         {
>             for(int j = 0 ; j<=m ; j++)
>             {
>                 if(j==0)
>                     dp[i][j] = 0 ;
>                 else if(i==0)
>                     dp[i][j] = INT_MAX/2 ;
>                 else if(B[i-1] <= j)
>                     dp[i][j] = min(C[i-1] + dp[i][j-B[i-1]] , dp[i-1][j]) ;
>                 else
>                     dp[i][j] = dp[i-1][j] ;
>                     
>                 //cout<<dp[i][j] <<" " ;
>             }
>             //cout<<endl ;
>         }
>         //cout<<endl ;
>         ans += dp[n][m] ;
>     }
>     
>     return ans ;
> }

#2

All friends use the same capacities and costs (B & C) arrays. So instead of building a new dp for every friend. We can use the same dp built for the highest capacity. For instance, in the example mentioned, we can build for dp[6][2], and just use the value of dp[4][2] from the same vector for the first friend.


#3

yes, I got what you are trying to say, but sometimes it is not easy to get your head around such things.
Basically, we are using the same arrays B and C and each friend’s min cost can be calculated independently or each cell in dp array with friend’s capacity , no of dishes represent the min cost for a particular friend.