C++ solution | 1D dp

[devansh-aggarwal_326]

int Solution::solve(const vector<int> &A, const vector<int> &B, const vector<int> &C) {
    int result = 0;
    int n = B.size();
    int maxCapacity = *(max_element(A.begin(), A.end()));
    
    // 1D dp: dp[i] => minimum money spent to fill ith capacity
    vector<int>dp(maxCapacity + 1);
    int costOfOneCapacityFood;
    for (int i = 0; i < B.size(); i++) {
        if (B[i] == 1) {
            costOfOneCapacityFood = i;
            break;
        }
    }
    /*
        For each capacity the worst case is when it is filled up
        with food of capacity 1
    */
    for(int i = 0; i <= maxCapacity; i++) {
        dp[i] = i*C[costOfOneCapacityFood];
    }
    
    // bottom-up dp
    for(int i = 0; i <= maxCapacity; i++) {
        for(int j = 0; j < n; j++) {
            if(i + B[j] <= maxCapacity) {
                dp[i + B[j]] = min(dp[i + B[j]], dp[i] + C[j]);
            }
        }
    }
    
    // adding cost for each friend
    for (int i : A) {
        result += dp[i];    
    }
    
    return result;
}