如何对无返回值(void)的递归函数进行Memoize记忆化处理

核心问题定位 #

你当前的递归逻辑是给数组每个元素分配正负号，求最终得到的最小非负总和，原暴力递归时间复杂度为O(2^n)，仅靠idx做记忆化是不可行的：同一idx下可能对应多个不同的sum值，必须把idx和当前累计和sum同时作为状态维度才能实现记忆化。

实现步骤 #

• 先计算数组所有元素的总和total，由于sum的取值范围是[-total, total]，存在负数值，需要给sum加total做偏移，把索引范围转为[0, 2*total]的非负整数，方便用数组做缓存
• 记忆化缓存memo[idx][offsetSum]存储处理到第idx个元素、当前累计和为sum时，后续能得到的最小非负总和，初始值设为-1表示未计算
• 把递归函数返回值改为int，直接返回当前状态的最优结果，取消全局变量ans，避免状态污染

优化后代码 #

class Solution {
    int total;
    int[][] memo;

    public int minimalNonNegativeSum(int[] arr) {
        total = 0;
        for (int num : arr) total += num;
        // 缓存维度：idx最大为arr.length，sum偏移后范围0~2*total
        memo = new int[arr.length + 1][2 * total + 1];
        // 初始化填充-1表示未计算
        for (int i = 0; i <= arr.length; i++) {
            for (int j = 0; j <= 2 * total; j++) {
                memo[i][j] = -1;
            }
        }
        return dfs(arr, 0, 0);
    }

    private int dfs(int[] arr, int idx, int sum) {
        // 边界：所有元素处理完
        if (idx == arr.length) {
            return sum >= 0 ? sum : Integer.MAX_VALUE / 2; // 除2防止后续加法溢出
        }
        // 计算偏移后的sum索引
        int offsetSum = sum + total;
        // 已计算过直接返回缓存结果
        if (memo[idx][offsetSum] != -1) {
            return memo[idx][offsetSum];
        }
        // 两种选择：加当前元素、减当前元素
        int chooseAdd = dfs(arr, idx + 1, sum + arr[idx]);
        int chooseSub = dfs(arr, idx + 1, sum - arr[idx]);
        // 存缓存并返回最小值
        memo[idx][offsetSum] = Math.min(chooseAdd, chooseSub);
        return memo[idx][offsetSum];
    }
}

注意事项 #

• 如果数组元素总和非常大，二维数组会占用较多内存，此时可以改用HashMap<String, Integer>做缓存，key拼接为idx + "_" + sum即可
• 该问题也可以转成01背包问题迭代实现，核心逻辑是求最接近总和一半的子集和，最终最小非负总和为total - 2*maxSubsetSum，熟悉记忆化递归后可以尝试迭代写法

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