在 java 代码中实现记忆时出错

Question

记忆化给我错误的答案。请有人帮我解决这个问题。在没有记忆的情况下，我在函数 targetBestR 中得到了正确的答案，但是在记忆函数 targetBestM 中，我得到了错误的值，这些值存储在相应键的数组列表中。

import java.util.ArrayList;

import java.util.HashMap;

public class TargetSumBest {

public static ArrayList<Integer> targetBestR(int n, int arr[]){
    if(n==0) return new ArrayList<Integer>();
    if(n<0) return null;
    ArrayList<Integer> shortestCombo=null;
    for(int i=0;i<arr.length;i++) {
        //System.out.println(i);
        //System.out.println(arr[i]);
        int rem=n-arr[i];
        //System.out.println(n+"-"+i+"="+rem);
        ArrayList<Integer> tar=targetBestR(rem, arr);
        if(tar!=null) {
            tar.add(arr[i]);
            if(shortestCombo==null||tar.size()<shortestCombo.size()) {
                shortestCombo=tar;
            }
        }
    }
    //System.out.println(n+"value"+shortestCombo);
    return shortestCombo;
}   
public static ArrayList<Integer> targetBestM(int n, int arr[], HashMap<Integer, ArrayList<Integer>> memo){
    if(n==0) return new ArrayList<Integer>();
    if(n<0) return null;
    if(memo.containsKey(n)) return memo.get(n);
    ArrayList<Integer> shortestCombo=null;
    for(int i=0;i<arr.length;i++) {
        //System.out.println(i);
        //System.out.println(arr[i]);
        int rem=n-arr[i];
        //System.out.println(n+"-"+i+"="+rem);
        ArrayList<Integer> tar=targetBestM(rem, arr,memo);
        if(tar!=null) {
            tar.add(arr[i]);
            if(shortestCombo==null||tar.size()<shortestCombo.size()) {
                shortestCombo=tar;
                
            }
        }
    }
    //System.out.println(n+"value"+shortestCombo);
    memo.put(n, shortestCombo);
    return shortestCombo;
}   
public static void main(String[] args) {
    int n=8; int arr[]= {1,4,2};
    
    System.out.println(targetBestM(n, arr, new HashMap<Integer, ArrayList<Integer>>()));
    System.out.println(targetBestR(n, arr));
}
}//error

Answer 1

能够找到问题所在。传入 HashMap 的数组不断被使用和添加。能够通过在从 HashMap 读取和写入时创建新的 ArrayLists 来修复它。

阅读时...

    if (memo.containsKey(n)) {
        System.out.println(indent + n +  " memo.get(n) = " + memo.get(n));
        return new ArrayList<>(memo.get(n));
    }

写作时...

    memo.put(n, new ArrayList<>(shortestCombo));

在 java 代码中实现记忆时出错

Getting an error while implementing memoization in the java code

java

dynamic-programming

memoization