使用DP求解Best Sum问题时加记忆化就出错该如何解决

问题原因 #

你的记忆化逻辑错误是因为修改了缓存中存储的列表对象：

• Java中List是引用类型，你存入map的是列表的内存地址，而非列表的副本
• 代码中List<Integer> t = rec(arr, rem, map)拿到结果后，直接执行t.add(i)修改了t本身，这会直接改变缓存中对应余数存储的列表内容，后续其他调用拿到这个被篡改的列表自然会得到错误结果
• 无记忆化时，每次递归返回的都是独立的列表对象，即使被修改也不会影响其他分支的计算，因此结果正确

修复方案 #

调整构造新列表的逻辑，不要修改递归返回的原列表即可：

public class BestSum {
    public static void main(String[] args) {
        int[] arr = { 2, 3, 4, 5 };
        int num = 10;
        Map<Integer, List<Integer>> map = new HashMap<>();
        List<Integer> list = rec(arr, num, map);
        System.out.println(list);
    }

    static List<Integer> rec(int[] arr, int n, Map<Integer, List<Integer>> map) {

        if (n == 0) {
            return new ArrayList<>();
        }
        if (n < 0) {
            return null;
        }
        if (map.containsKey(n)) {
            return map.get(n);
        }
        List<Integer> sCombo = null;
        for (int i : arr) {
            int rem = n - i;
            List<Integer> t = rec(arr, rem, map);
            if (t != null) {
                // 先复制返回的列表，再添加当前元素，不修改原t
                List<Integer> list = new ArrayList<>(t);
                list.add(i);
                if (sCombo == null || list.size() < sCombo.size()) {
                    sCombo = list;
                }

            }
        }

        map.put(n, sCombo);
        return sCombo;
    }
}

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