题目链接

题目描述

image.png
image.png
image.png

思路：暴力DFS

https://leetcode-cn.com/problems/shopping-offers/solution/tong-ge-lai-shua-ti-la-yi-ti-liang-jie-b-2ccb/
首先，观察本题给定的数据范围非常小，我们可以先尝试使用暴力求解，使用暴力的突破口是我们需要的物品数量，每当递归一次，我们就把需要的物品数量减少一次，当然，我们的每一次递归中有两个分支，即不使用礼包和使用一个礼包。

请看代码，加了详细注释：

  1. class Solution {
  3.     int n;
  5.     public int shoppingOffers(List<Integer> price, 
  6.                               List<List<Integer>> special, 
  7.                               List<Integer> needs) {
  8.         this.n = price.size();
  9.         return dfs(price, special, needs);
  10.     }
  12.     private int dfs(List<Integer> price, 
  13.                     List<List<Integer>> special, 
  14.                     List<Integer> needs) {
  15.         // 不使用大礼包的情况下
  16.         int ans = 0;
  17.         for (int i = 0; i < n; i++) {
  18.             ans += needs.get(i) * price.get(i);
  19.         }
  21.         // 使用大礼包的情况下
  22.         for (List<Integer> s : special) {
  23.             // 大礼包可以购买无限次
  24.             // 这里相当于深拷贝一个新的List出来，所以，下面不用恢复状态了
  25.             List<Integer> curr = new ArrayList<>(needs);
  26.             boolean flag = false;
  27.             for (int i = 0; i < n; i++) {
  28.                 // 判断是否超出数量限制
  29.                 if (curr.get(i) - s.get(i) < 0) {
  30.                     flag = true;
  31.                     break;
  32.                 }
  33.                 curr.set(i, curr.get(i) - s.get(i));
  34.             }
  36.             // 未超出数量限制
  37.             if (!flag) {
  38.                 // 选定这个礼包，并继续递归
  39.                 ans = Math.min(ans, s.get(n) + dfs(price, special, curr));   
  40.             }
  41.         }
  43.         return ans;
  44.     }
  45. }

思路二：记忆化搜索

其实，仔细分析上面的暴力解法，对于每一种需求数量，会出现重复计算，所以，我们可以加上记忆化的逻辑，遇到同一种状态，可以直接返回，提高效率。

  1. class Solution {
  3.     int n;
  5.     public int shoppingOffers(List<Integer> price, 
  6.                               List<List<Integer>> special, 
  7.                               List<Integer> needs) {
  8.         this.n = price.size();
  9.         Map<List<Integer>, Integer> cache = new HashMap<>();
  10.         return dfs(price, special, needs, cache);
  11.     }
  13.     private int dfs(List<Integer> price, 
  14.                     List<List<Integer>> special, 
  15.                     List<Integer> needs, 
  16.                     Map<List<Integer>, Integer> cache) {
  17.         if (cache.containsKey(needs)) {
  18.             return cache.get(needs);
  19.         }
  21.         // 不使用大礼包的情况下
  22.         int ans = 0;
  23.         for (int i = 0; i < n; i++) {
  24.             ans += needs.get(i) * price.get(i);
  25.         }
  27.         // 使用大礼包的情况下
  28.         for (List<Integer> s : special) {
  29.             // 大礼包可以购买无限次
  30.             List<Integer> curr = new ArrayList<>(needs);
  31.             boolean flag = false;
  32.             for (int i = 0; i < n; i++) {
  33.                 // 判断是否超出数量限制
  34.                 if (curr.get(i) - s.get(i) < 0) {
  35.                     flag = true;
  36.                     break;
  37.                 }
  38.                 curr.set(i, curr.get(i) - s.get(i));
  39.             }
  41.             // 未超出数量限制
  42.             if (!flag) {
  43.                 ans = Math.min(ans, s.get(n) + dfs(price, special, curr, cache));   
  44.             }
  45.         }
  47.         cache.put(needs, ans);
  49.         return ans;
  50.     }
  51. }

反思

我是废物