638. 大礼包

完全背包 + 状压 + 记忆化搜索

class Solution {
public:
    vector<vector<int>>special;
    vector<unordered_map<int, int>> f;
    vector<int>price;
    int n;
    int dp(int x, int y){
        if(f[x].count(y)) return f[x][y];
        if(!x){
            f[x][y] = 0;
            for(int i = n - 1; i >= 0; --i){
                int c = y >> i * 4 & 15;   // 取16进制位数
                f[x][y] += c * price[i];
            }
            return f[x][y];
        } 
        f[x][y] = dp(x - 1, y);
        int v = 0;
        for(int j = n - 1; j >= 0; --j){
            int c = y >> j * 4 & 15;
            if(c < special[x - 1][j]){
                v = -1;
                break;
            }
            v = v * 16 + c - special[x - 1][j];
        }
        if(~v)f[x][y] = min(f[x][y], dp(x, v) + special[x - 1].back());
        return f[x][y];
    }
    int shoppingOffers(vector<int>& _price, vector<vector<int>>& _special, vector<int>& needs) {
        //直接完全背包状态数过多，利用记忆化搜索解决(可以省去一些对结果无法无意义的状态)
        price = _price, special = _special;
        n = price.size();
        int state = 0;
        f = vector<unordered_map<int, int>>(special.size() + 1,  unordered_map<int, int>());//状压成16进制数,用哈希表减少状态数
        for(int i = needs.size() - 1; i >= 0; --i) state = state * 16 + needs[i];
        return dp(special.size(), state);
    }
};