LeetCode 3366：Minimum Array Sum递归解法失效求助

题目描述 #

给定整数数组nums和三个整数k、op1、op2，可执行两种操作：

• 操作1：选择索引i，将nums[i]向上取整除以2，最多执行op1次，每个索引最多执行一次。
• 操作2：选择索引i，若nums[i]≥k则减去k，最多执行op2次，每个索引最多执行一次。

两种操作可作用于同一索引各一次，求操作后数组的最小可能和。

问题代码 #

class Solution {
public:

    int fun(int ind, vector<int>&nums, int op1,int op2, int k){

        if(ind<0){
            return 0;
        }
        if(op1<=0 and op2<=0){
            int sum =0;
            while(ind>=0){
                sum+=nums[ind];
                ind--;
            }
            return sum;
        }
        
        int x=INT_MAX,y=INT_MAX,z=INT_MAX;
        int curr=nums[ind];
        if(op2>0 and nums[ind]>=k){
            x = nums[ind]-k + fun(ind-1,nums,op1,op2-1,k);
        }
        if(op1>0){
            int temp = curr%2? curr/2 : (curr/2) +1;
            y = temp + fun(ind-1,nums, op1-1,op2,k);
        }
        if(op2>0 and curr>=k and op1>0){
            int temp1 = (curr-k)%2? (curr-k)/2: ((curr-k)/2)+1;
            int temp2 = curr %2 ? curr/2 -3: curr/2 -2;
            z = min(temp1,temp2) + fun(ind-1,nums,op1-1,op2-1,k);
        }
        
        return min({x,y,z,nums[ind]});
    }

    int minArraySum(vector<int>& nums, int k, int op1, int op2) {
        sort(nums.begin(),nums.end());
        return fun(nums.size()-1,nums,op1,op2,k);
    }
};

错误点排查 #

1. 操作1的向上取整计算完全错误 #

原代码中操作1的计算逻辑：

int temp = curr%2? curr/2 : (curr/2) +1;

这与向上取整除以2的逻辑完全相反：

• 当curr为奇数时（比如5），向上取整除以2应该是3，但代码返回5/2=2，结果偏小。
• 当curr为偶数时（比如4），向上取整除以2应该是2，但代码返回4/2+1=3，结果偏大。
  正确的向上取整除以2的计算应该是：(curr + 1) / 2（整数除法下，奇数加1后除以2就是向上取整，偶数加1除以2也等于原数除以2）。

2. 同时执行两种操作的逻辑无意义 #

原代码中temp2的计算：

int temp2 = curr %2 ? curr/2 -3: curr/2 -2;

这部分没有任何逻辑依据，既不是先执行操作1再执行操作2的结果，也不是合理的计算。同时执行两种操作的正确逻辑是：

• 先执行操作2再执行操作1：((curr -k) +1)/2（正确的向上取整除以2）。
• 先执行操作1再执行操作2：如果(curr+1)/2 >=k，则结果是(curr+1)/2 -k，否则只能选择先执行操作2再执行操作1。
  需要分别计算这两种合法顺序的结果，再取最小值，而不是用无意义的减法。

3. 不执行任何操作的选项错误 #

原代码返回时包含nums[ind]，这意味着直接取当前元素的值，且不处理后续元素，完全不符合递归逻辑。正确的不执行操作的选项应该是：

int no_op = nums[ind] + fun(ind-1, nums, op1, op2, k);

即当前元素保持原样，递归处理前面的元素。

4. 同时执行操作时的temp1计算错误 #

原代码中temp1的计算同样搞反了奇偶的处理：

int temp1 = (curr-k)%2? (curr-k)/2: ((curr-k)/2)+1;

正确的向上取整除以2应该是((curr -k) +1)/2。

5. 缺少记忆化（性能隐患） #

当前递归没有使用记忆化缓存，对于较大的数组和操作次数，会出现大量重复计算，导致超时。可以用memo[ind][op1][op2]来缓存已经计算过的状态，避免重复递归。

修正后的核心逻辑示例 #

以操作1和同时操作的修正为例：

// 修正操作1的计算
if(op1>0){
    int temp = (curr +1)/2; // 正确的向上取整除以2
    y = temp + fun(ind-1,nums, op1-1,op2,k);
}

// 修正同时执行两种操作的逻辑
if(op2>0 and curr>=k and op1>0){
    // 先op2再op1
    int val1 = ((curr -k) +1)/2;
    // 先op1再op2：需要判断op1后的结果是否>=k
    int op1_val = (curr +1)/2;
    int val2 = INT_MAX;
    if(op1_val >=k){
        val2 = op1_val -k;
    } else {
        // 先op1后无法执行op2，所以只能选先op2再op1
        val2 = val1;
    }
    z = min(val1, val2) + fun(ind-1,nums,op1-1,op2-1,k);
}

// 修正不执行操作的选项
int no_op = nums[ind] + fun(ind-1, nums, op1, op2, k);
return min({x,y,z,no_op});

内容的提问来源于stack exchange，提问作者snehith oddula