Clean top-down DP in C++


#1

Clean Top-Down DP:

int Solution::solve(const vector<int> &A, const vector<int> &B, const vector<int> &C) {
    vector<pair<int,int> > v;
    for(int i=0;i<B.size();i++){
        v.push_back(make_pair(B[i],C[i]));
    }
    sort(v.begin(),v.end());
    int dp[B.size()][1000+1];
    for(int j=0;j<B.size();j++){
        dp[j][0]=0;
    }
    for(int j=0;j<=1000;j++){
        dp[0][j]=v[0].second*j;
    }
    for(int i=1;i<B.size();i++){
        for(int bhukh=1;bhukh<=1000;bhukh++){
            if(bhukh>=v[i].first){
                dp[i][bhukh]=min(dp[i-1][bhukh],dp[i][bhukh-v[i].first]+v[i].second);
            }else{
                dp[i][bhukh]=dp[i-1][bhukh];
            }
        }
    }
    int ans=0;
    for(auto ind_bhukh:A){
        ans+=dp[B.size()-1][ind_bhukh];
    }
    return ans;
}