C++ top-down DP solution


  • 0
    M

    The idea is easy but a little verbose to implement for me. And the special may be even more expensive than buying separately, that's quite amusing....

        vector<bool> check;
        map<vector<int>, int> dp;
        int shoppingOffers(vector<int>& price, vector<vector<int>>& special, vector<int>& needs) {
            for(int i=0;i<special.size();i++) {
                int temp=0, j=0;
                for(j;j<special[i].size()-1;j++) temp+=price[j]*special[i][j];
                check.push_back(temp>special[i][j]);
            }
            return DP(price, special, needs);
        }
        
        int DP(vector<int>& p, vector<vector<int>>& s, vector<int> n) {
            int res=INT_MAX;
            for(int i=0;i<s.size();i++) {
                bool f=true;
                vector<int> t=n;
                for(int j=0;j<s[i].size()-1;j++) {
                    t[j]-=s[i][j];
                    if(t[j]<0) {
                        f=false;
                        break;
                    }
                }
                if(f==false||!check[i]) {
                    int temp=0;
                    for(int j=0;j<t.size();j++) temp+=n[j]*p[j];
                    dp[t]=temp;
                    res=min(res, temp);
                }
                else {
                    if(dp.find(t)==dp.end()) dp[t]=DP(p, s, t);
                    res=min(res, dp[t]+s[i][s[i].size()-1]);
                }
            }
            return res;
        }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.