638. 大礼包 Krains 2020-08-01 19:48:29 动态规划DFS

# 题目链接

# DFS加记忆化

解题思路

• 将原价物品打包成大礼包，统一进行处理
• 如果最优解中包含一种大礼包，那么该大礼包一定是买到不能买为止的。
• 使用DFS搜索所有可能购买的方案，对于相同的needs来说最优解是一定的，所以可以加记忆化。

代码语言：javascript复制

class Solution {
    Map<List<Integer>, Integer> memo = new HashMap<>();

    public int shoppingOffers(List<Integer> price, List<List<Integer>> special, List<Integer> needs) {
        // 将原价物品也打包成大礼包，方便处理
        for(int i = 0; i < price.size(); i  ){
            List<Integer> list = new ArrayList<>();
            for(int j = 0; j < price.size(); j  ){
                if(j != i) 
                    list.add(0);
                else
                    list.add(1);
            }
            list.add(price.get(i));
            special.add(list);
        }

        // 将needs全为0状态放入
        List<Integer> list = new ArrayList<>();
        for(int i = 0; i < needs.size(); i  )
            list.add(0);
        memo.put(list, 0);

        return helper(special, needs);
    }

    public int helper(List<List<Integer>> special, List<Integer> needs) {
        if(memo.containsKey(needs))
            return memo.get(needs);

        int i;
        int cost = (int)1e8;
        for(List<Integer> list : special){
            // k为最多购买k件当前大礼包
            int k = (int)1e8;
            for(i = 0; i < list.size()-1; i  ){
                if(list.get(i) != 0){
                    k = Math.min(k, needs.get(i) / list.get(i));
                }
            }
            // 如果当前礼包无法购买，考虑下一个礼包
            if(k == 0)
                continue;

            // 购买k件当前大礼包
            List<Integer> temp = new ArrayList<>();
            for(i = 0; i < list.size() - 1; i  )
                temp.add(needs.get(i) - k * list.get(i));
            cost = Math.min(cost, helper(special, temp)   k * list.get(i));
        }
        
        // 记忆
        memo.put(needs, cost);
        return cost;
    }
}

打包 dfs 搜索

0 人点赞