Steward

分享是一種喜悅、更是一種幸福

程式語言 - LeetCode - CPP - 638. Shopping Offers

---

題目：


解答：

class Solution {
public:
    int shoppingOffers(vector<int>& price, vector<vector<int>>& special, vector<int>& needs) {
        map<vector<int>, int> memo;

        auto dfs = [&](this auto&& dfs, vector<int> new_needs) {
            if (memo.count(new_needs)) {
                return memo[new_needs];
            }

            int ans = 0;

            for (int i = 0; i < price.size(); ++i) {
                ans += new_needs[i] * price[i];
            }

            for (auto& offer : special) {
                bool valid = true;
                vector<int> nx = new_needs;

                for (int i = 0; i < needs.size(); ++i) {
                    if (nx[i] < offer[i]) {
                        valid = false;
                        break;
                    }

                    nx[i] -= offer[i];
                }

                if (valid) {
                    ans = min(ans, offer.back() + dfs(nx));
                }
            }

            return memo[new_needs] = ans;
        };

        return dfs(needs);
    }
};