C++ Straightforward memorization solution


  • 0
    K

    it seems straightforward memorization solution. 6 parameters related to the item in the function made it very straightforward to understand how it work.

    class Solution {
        int dp[7][7][7][7][7][7];
    public:
        int solve(vector<int>& prices, vector<vector<int>>& special, int a, int b, int c, int d, int e, int f) {
            if (a < 0 || b < 0 || c < 0 || d < 0 || e < 0 || f < 0) {
                return 9999999;
            }
            int& ret = dp[a][b][c][d][e][f];
            if (ret != 0) {
                return ret;
            }
            ret = (prices[0] * a) + (prices[1] * b) + (prices[2] * c) + (prices[3] * d) + (prices[4] * e) + (prices[5] * f);
            int itemCnt = special[0].size() - 1;
            for (int i = 0; i < special.size(); i++) {
                int ta = itemCnt > 0 ? special[i][0] : 0;
                int tb = itemCnt > 1 ? special[i][1] : 0;
                int tc = itemCnt > 2 ? special[i][2] : 0;
                int td = itemCnt > 3 ? special[i][3] : 0;
                int te = itemCnt > 4 ? special[i][4] : 0;
                int tf = itemCnt > 5 ? special[i][5] : 0;
                ret = min(ret, solve(prices, special, a - ta, b - tb, c - tc, d - td, e - te, f - tf) + special[i].back());
            }
            return ret;
        }
    
        int shoppingOffers(vector<int>& price, vector<vector<int>>& special, vector<int>& needs) {
            int i, j, k, l, m, n;
            if (price.size() < 6) {
                for (i = price.size(); i < 6; i++) {
                    price.push_back(0);
                    needs.push_back(0);
                    for (j = 0; j < special.size(); j++) {
                    }
                }
            }
            return solve(price, special, needs[0], needs[1], needs[2], needs[3], needs[4], needs[5]);
        }
    }
    

Log in to reply
 

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