LeetCode装满石头的最大背包数：递归/记忆化解法错误排查

题目描述 #

给定两个数组capacity（背包最大容量）、rocks（当前石头数），以及额外石头数additionalRocks，返回能装满的最大背包数量。
示例输入：capacity = [2,3,4,5]，rocks = [1,2,4,4]，additionalRocks = 2，输出3。

尝试过程 #

已知贪心排序可解，但尝试递归思路：选择填满当前背包或不填，递归处理下一索引，但递归版本因指数复杂度超时。随后添加基于HashMap的记忆化（用索引i和剩余额外石头数拼接字符串作为键），但该版本仅通过27/79测试用例，无法确定问题出在递归逻辑还是记忆化实现。

递归代码 #

class Solution {
    int[] capacities;
    int[] current;
    
    private int helper(int i,int addrocks){
        if(i>=capacities.length) return 0;
        
        if(addrocks <= 0) return 0;
        
        int ans1=0;
        if(addrocks>=(capacities[i]-current[i])){
            ans1 = 1 + helper(i+1,addrocks-(capacities[i]-current[i]));
        }
        
       int ans2 = helper(i+1,addrocks);
        
        return Math.max(ans1,ans2);
    }
    
    public int maximumBags(int[] capacity, int[] rocks, int additionalRocks) {
        capacities = capacity;
        current = rocks;
        return helper(0,additionalRocks);
    }
}

记忆化代码 #

class Solution {
    int[] capacities;
    int[] current;
    Map<String,Integer> m;
    
    private int helper(int i,int addrocks){
        if(i>=capacities.length) return 0;
        
        if(addrocks <= 0) return 0;
        
        StringBuilder sb = new StringBuilder();
        sb.append(i); sb.append("i"); sb.append(addrocks); sb.append("r");
        String x = sb.toString();
        if(m.containsKey(x)){
            return m.get(x);
        }
        
        int ans1=0;
        if(addrocks>=(capacities[i]-current[i])){
            ans1 = 1 + helper(i+1,addrocks-(capacities[i]-current[i]));
        }
        
        int ans2 = helper(i+1,addrocks);
        int maxans = Math.max(ans1,ans2);
        m.put(x,maxans);
        return maxans;
    }
    
    public int maximumBags(int[] capacity, int[] rocks, int additionalRocks) {
        capacities = capacity;
        current = rocks;
        m = new HashMap<>();
        return helper(0,additionalRocks);
    }
}

问题根源 #

1. 递归逻辑错误：当addrocks <= 0时直接返回0是核心问题。即使没有额外石头，前面已经装满的背包数量需要保留，而不是重置为0。比如处理到第i个背包时已经装满了k个，此时额外石头用完，应该返回k而非0。
2. 记忆化键的歧义风险：字符串拼接时用i和r分隔，若i或addrocks是多位数，可能出现键冲突（比如i=12、addrocks=3与i=1、addrocks=23会生成相同的键）。

修正后的递归+记忆化代码 #

class Solution {
    int[] capacities;
    int[] current;
    Map<String, Integer> memo;
    
    private int helper(int i, int addrocks) {
        if (i >= capacities.length) {
            return 0;
        }
        
        // 用|分隔避免数值拼接歧义
        String key = i + "|" + addrocks;
        if (memo.containsKey(key)) {
            return memo.get(key);
        }
        
        // 不填当前背包的情况
        int skip = helper(i + 1, addrocks);
        
        // 尝试填满当前背包的情况
        int fill = 0;
        int needed = capacities[i] - current[i];
        if (addrocks >= needed) {
            fill = 1 + helper(i + 1, addrocks - needed);
        }
        
        int max = Math.max(skip, fill);
        memo.put(key, max);
        return max;
    }
    
    public int maximumBags(int[] capacity, int[] rocks, int additionalRocks) {
        capacities = capacity;
        current = rocks;
        memo = new HashMap<>();
        return helper(0, additionalRocks);
    }
}

最优解：贪心算法 #

递归+记忆化的时间复杂度为O(n * additionalRocks)，当additionalRocks数值很大时效率极低。贪心算法时间复杂度为O(n log n)，是更优选择：

import java.util.Arrays;

class Solution {
    public int maximumBags(int[] capacity, int[] rocks, int additionalRocks) {
        int n = capacity.length;
        int[] gaps = new int[n];
        for (int i = 0; i < n; i++) {
            gaps[i] = capacity[i] - rocks[i];
        }
        Arrays.sort(gaps);
        
        int count = 0;
        for (int gap : gaps) {
            if (additionalRocks >= gap) {
                additionalRocks -= gap;
                count++;
            } else {
                break;
            }
        }
        return count;
    }
}

内容的提问来源于stack exchange，提问作者Jeff Hamilton