大礼包 图解题解

这道题到底在问什么

输入

price=[2,5], 礼包=[3A0B¥5],[1A2B¥10], needs=[3,2]

输出

14

输入

price=[2,3,4], 礼包=[1A1B¥4],[2A2B1C¥9], needs=[1,2,1]

输出

11

最优解：一步一步想明白

1. 3核心一句话:状态是「还需向量」,答案 = min(原价单买, 每个买得起的礼包价 + 递归剩余)。算过就记下来。
2. 4先把输入摆上台:要买 3 个 A、2 个 B,写成状态 [3,2]。右边面板是备忘录,现在空着。下面从顶层 dfs([3,2]) 开始递归。
3. 5进入第一层 dfs([3,2])。按套路,第一步永远先算不用任何礼包的原价兜底,心里有个底再去试礼包。
4. 6原价单买 3 个 A、2 个 B 共 16 元,先把当前最优 ans 记成 16。礼包只是可选项,这个 16 必须先占着位置。
5. 7试礼包1:每件拿的数量都不超过当前还需,买得起。能不能买只看会不会超买,划不划算交给后面取最小。
6. 8买下礼包1,扣掉 3 个 A,清单从 [3,2] 变成 [0,2],先付礼包价 5 元,剩下的 [0,2] 丢给下一层递归。
7. 9进入第二层 dfs([0,2]):A 不用买了,只要凑齐 2 个 B。流程照旧,先算原价兜底再逐个试礼包。
8. 10这层原价兜底:A 要 0 个不花钱,B 要 2 个共 10 元。先把这层 ans 记成 10,再看礼包能不能帮上忙。
9. 11试礼包1,它要 3 个 A,可现在 A 的还需已是 0,拿不出 3 个,一买就超买,买不起,直接跳过。
10. 12再试礼包2,它要 1 个 A,A 的还需仍是 0,连 1 个都拿不出,同样超买。礼包2 也买不起。
11. 13dfs([0,2]) 两个礼包都买不起,只能用兜底 10 元。把状态 [0,2] 对应 10 元记进备忘录,返回上一层。
12. 14结果回到 dfs([3,2])。走礼包1 这条路 = 礼包价 5 + 子状态 [0,2] 的 10 = 15 元,比 16 省,ans 更新成 15。
13. 15试礼包2:还需 A=3≥1、还需 B=2≥2,两件都不超买,正好都够,礼包2 买得起。
14. 16买下礼包2,扣掉 1 个 A、2 个 B,清单从 [3,2] 变成 [2,0],先付 10 元,剩下的 [2,0] 丢给下一层。
15. 17进入 dfs([2,0]),只要凑齐 2 个 A。套路照旧,先兜底再试礼包,这次走快一点。
16. 18原价兜底:2 个 A 每个 2 元共 4 元,B 不用买。这层 ans 先记成 4。
17. 19礼包1 要 3 个 A,可手上只还需 2 个 A,凑不够 3,买了就超清单,买不起。
18. 20礼包2 要 2 个 B,而 B 的还需已是 0,一个都不能再买,这回卡在 B 上,也买不起。
19. 21两个礼包又都落空,dfs([2,0]) 用兜底 4 元。把 [2,0] 对应 4 元记进备忘录,返回上一层。备忘录攒到两条。
20. 22回到 dfs([3,2])。走礼包2 这条路 = 礼包价 10 + 子状态 [2,0] 的 4 = 14 元,比 15 省,ans 更新成 14。
21. 23dfs([3,2]) 能试的礼包全试过,最低花费锁定 14 元。把顶层状态 [3,2] 对应 14 记进备忘录,返回主程序。三个状态全算完。
22. 24回看备忘录三条记录都在。本例每个状态只出现一次,但商品、礼包一多,同一剩余状态会被反复递归到,那时直接取值,这正是记忆化的价值。
23. 25最优买法:花 10 元买礼包2 拿到 1A2B,剩下 2 个 A 原价单买 4 元,合计 14 元,比原价单买的 16 元省了 2 元。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

from __future__ import annotations
from typing import *
from collections import *
from functools import *
from itertools import *
from math import *
from heapq import *
from bisect import *
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
class Solution:
    def shoppingOffers(
        self, price: List[int], special: List[List[int]], needs: List[int]
    ) -> int:
        @cache
        def dfs(cur: int) -> int:
            ans = sum(p * (cur >> (i * bits) & 0xF) for i, p in enumerate(price))
            for offer in special:
                nxt = cur
                for j in range(len(needs)):
                    if (cur >> (j * bits) & 0xF) < offer[j]:
                        break
                    nxt -= offer[j] << (j * bits)
                else:
                    ans = min(ans, offer[-1] + dfs(nxt))
            return ans

        bits, mask = 4, 0
        for i, need in enumerate(needs):
            mask |= need << i * bits
        return dfs(mask)

#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <optional>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
struct TreeNode {
  int val;
  TreeNode *left;
  TreeNode *right;
  TreeNode() : val(0), left(nullptr), right(nullptr) {}
  TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
  TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};
struct ListNode {
  int val;
  ListNode *next;
  ListNode() : val(0), next(nullptr) {}
  ListNode(int x) : val(x), next(nullptr) {}
  ListNode(int x, ListNode *next) : val(x), next(next) {}
};
class Solution {
public:
    int shoppingOffers(vector<int>& price, vector<vector<int>>& special, vector<int>& needs) {
        const int bits = 4;
        int n = needs.size();
        unordered_map<int, int> f;
        int mask = 0;
        for (int i = 0; i < n; ++i) {
            mask |= needs[i] << (i * bits);
        }
        function<int(int)> dfs = [&](int cur) {
            if (f.find(cur) != f.end()) {
                return f[cur];
            }
            int ans = 0;
            for (int i = 0; i < n; ++i) {
                ans += price[i] * ((cur >> (i * bits)) & 0xf);
            }
            for (const auto& offer : special) {
                int nxt = cur;
                bool ok = true;
                for (int j = 0; j < n; ++j) {
                    if (((cur >> (j * bits)) & 0xf) < offer[j]) {
                        ok = false;
                        break;
                    }
                    nxt -= offer[j] << (j * bits);
                }
                if (ok) {
                    ans = min(ans, offer[n] + dfs(nxt));
                }
            }
            f[cur] = ans;
            return ans;
        };
        return dfs(mask);
    }
};

import java.util.*;
class TreeNode { int val; TreeNode left; TreeNode right; TreeNode(){} TreeNode(int val){this.val=val;} TreeNode(int val, TreeNode left, TreeNode right){this.val=val;this.left=left;this.right=right;} }
class ListNode { int val; ListNode next; ListNode(){} ListNode(int val){this.val=val;} ListNode(int val, ListNode next){this.val=val;this.next=next;} }
class Solution {
    private final int bits = 4;
    private int n;
    private List<Integer> price;
    private List<List<Integer>> special;
    private Map<Integer, Integer> f = new HashMap<>();

    public int shoppingOffers(
        List<Integer> price, List<List<Integer>> special, List<Integer> needs) {
        n = needs.size();
        this.price = price;
        this.special = special;
        int mask = 0;
        for (int i = 0; i < n; ++i) {
            mask |= needs.get(i) << (i * bits);
        }
        return dfs(mask);
    }

    private int dfs(int cur) {
        if (f.containsKey(cur)) {
            return f.get(cur);
        }
        int ans = 0;
        for (int i = 0; i < n; ++i) {
            ans += price.get(i) * (cur >> (i * bits) & 0xf);
        }
        for (List<Integer> offer : special) {
            int nxt = cur;
            boolean ok = true;
            for (int j = 0; j < n; ++j) {
                if ((cur >> (j * bits) & 0xf) < offer.get(j)) {
                    ok = false;
                    break;
                }
                nxt -= offer.get(j) << (j * bits);
            }
            if (ok) {
                ans = Math.min(ans, offer.get(n) + dfs(nxt));
            }
        }
        f.put(cur, ans);
        return ans;
    }
}

复杂度

面试官可能追问