638. Shopping Offers

题目

题意

不同的商品i有不同需求needs[i]
有些特价组合special[],对应每一种商品i有相应的数量,买相应的数量就可以用组合价(但是有一些组合未必会比单买便宜)
求恰好买够需求needs[]的的最低总价.

分析

用动态规划+DFS
每一次调用遍历一次组合special[i], 看剩余的需求里面能不能用组合i的方式购买,如果可以,则使用组合i,并且减去相应的need的数量,剩余的数量再调用一次递归, 然后继续循环

实现

class Solution {
public:
    bool checkvalid(vector<int>& needs, const vector<int>& special) {
        for (int j = 0; j < needs.size(); ++j) {
                if (needs[j]-special[j] < 0) {
                    return false;
                }
        }
        return true;
    }
    int shoppingOffers(vector<int>& price, vector<vector<int>>& special, vector<int>& needs) {
        int minPrice = 0;
        for (int i = 0; i < needs.size(); ++i) {
            minPrice += needs[i]*price[i];
        }

        for (int i = 0; i < special.size(); ++i) {
            if (checkvalid(needs, special[i])) {
                vector<int> curNeeds;
                for (int j = 0; j < needs.size(); ++j) {
                    curNeeds.push_back(needs[j]-special[i][j]);
                }
                int tempPrice = shoppingOffers(price, special, curNeeds)+special[i].back();
                minPrice = min(minPrice, tempPrice);
            }
        }

        return minPrice;
    }
};