638. 大礼包

思路

设dp[needs]表示每个物品数量为$needs_{i}$的最低价格

那么有两种转移方式：

  • 购买大礼包

    首先需要考虑所有物品的需要的数量都需要小于大礼包中物品的数量才能进行购买

    $dp[needs]=min(dp[needs-needs_{i}]+price_{i})$,i表示大礼包的下标

  • 直接购买商品

考虑记忆化搜索

Solutions
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
class Solution {
public:
    vector<int> needs_;
    vector<int> price_;
    vector<vector<int> > special_;
    int n;
    map<vector<int>, int> dp;
    int shoppingOffers(vector<int>& price, vector<vector<int>>& special, vector<int>& needs) {
        price_ = price;
        special_ = special;
        n = needs.size();
        return dfs(needs);
    }
    int dfs(vector<int> needs) {
        if (dp.count(needs) != 0)
            return dp[needs];

        int Min = 0;
        for (int i = 0; i < needs.size(); i++)
            Min += needs[i] * price_[i];

        for (int i = 0; i < special_.size(); i++) {
            vector<int> nextNeeds = needs;
            bool flag = true;
            for (int j = 0; j < n; j++) {
                if (special_[i][j] > nextNeeds[j])
                    flag = false;
                nextNeeds[j] -= special_[i][j];
            }
            if (!flag)
                continue;
            Min = min(Min, dfs(nextNeeds) + special_[i][n]);
        }
        return dp[needs] = Min;
    }
};