为何给递归函数添加Memoization后输出结果不一致？

有人能解释为何以下两个函数输出结果不同吗？我尝试为递归函数添加Memoization，但添加后输出值发生了变化。这是不是意味着相同子问题返回了不同结果？我十分困惑，恳请各位帮忙解答。

未添加记忆化的版本 #

public long maxAlternatingSumHelper(int[] nums,int index,boolean plus, long sum) {
    if (index == nums.length) {
        return sum;
    }
   
    int adder = nums[index];
    if (!plus) adder *= -1;
    long ans = Math.max(maxAlternatingSumHelper(nums,index+1,true, 0),
            Math.max(maxAlternatingSumHelper(nums,index+1,plus, sum),
             maxAlternatingSumHelper(nums,index+1,!plus, sum + adder)));
    return ans;
}

添加记忆化的版本 #

Hashtable<IndexPlus,Long> sumDp = new Hashtable<>();
public long maxAlternatingSumHelper(int[] nums,int index,boolean plus, long sum) {
    if (index == nums.length) {
        return sum;
    }
    if (sumDp.containsKey(new IndexPlus(index,plus))){
        return sumDp.get(new IndexPlus(index,plus));
    }
    int adder = nums[index];
    if (!plus) adder *= -1;
    long ans = Math.max(maxAlternatingSumHelper(nums,index+1,true, 0),
            Math.max(maxAlternatingSumHelper(nums,index+1,plus, sum),
             maxAlternatingSumHelper(nums,index+1,!plus, sum + adder)));
    sumDp.put(new IndexPlus(index,plus),ans);
    return ans;
}

问题根源分析 #

• 记忆化键值不完整：当前缓存键只包含index和plus，但递归函数的返回值完全依赖sum参数。相同的index和plus，如果传入的sum不同，计算结果必然不同。用同一个键缓存不同sum下的结果，后续调用会直接返回错误的缓存值，导致输出偏差。
• 递归分支的缓存冲突：第一个递归分支maxAlternatingSumHelper(nums,index+1,true, 0)强制将sum重置为0，当这个分支的结果被缓存后，后续所有相同index和plus的调用都会复用这个重置后的结果，完全忽略了当前实际传入的sum，这是输出异常的核心触发点。
• 正确的记忆化方向：要么把sum也纳入缓存键（需要确保IndexPlus类正确实现equals和hashCode方法，包含sum字段），要么重构递归逻辑——让函数返回从当前index、plus状态出发能得到的最大交替和，把sum的累加逻辑转化为函数的返回值状态，而非通过参数传递。

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