bestSum -动态规划

Question

我试图解决bestSum的问题，它基本上找到了与目标值相加的最小元素数量，下面的内容似乎很好，

示例输出，bestSum(10，新int[]{1，2，5})应该是pring [5，5]。

static List<Integer> bestSumNoDp(int target, int[] nums) {
    if (target == 0) return new ArrayList<>();
    if (target < 0) return null;

    List<Integer> shortest = null;
    for (Integer num : nums) {
        List<Integer> list = bestSumNoDp(target-num, nums);
        if (list != null) {
            list.add(num);
            if (shortest == null || shortest.size() > list.size())
                shortest = list;
        }
    }
    return shortest;
}

当我尝试实现DP版本时，我遇到了一个问题，我注意到当我打印缓存时，打印中有一个"Top"，一个额外的元素被添加了，我不知道为什么，我做错了什么？

    static ArrayList bestSum(int target, int[] nums) {
        return bestSum(target, nums, new ArrayList[target+1]);
    }

    static ArrayList<Integer> bestSum(int target, int[] nums, ArrayList<Integer>[] cache) {
        if (target == 0) return new ArrayList<>();
        if (target < 0) return null;
        //System.out.println("Top - Target " + target + " Cache " + cache[target]); //Debugging

        if (cache[target] != null) return cache[target];
        
        ArrayList<Integer> shortest = null;
        for (Integer num : nums) {
            ArrayList<Integer> list = bestSum(target-num, nums, cache);
            if (list != null) {
                list.add(num);
                if (shortest == null || shortest.size() > list.size())
                    shortest = list;
            }
        }

//        cache[target] = null;//
//        cache[target] = (ArrayList<Integer>) shortest.clone(); //Didn't help
//        cache[target] = shortest;//Didn't help
        cache[target] = new ArrayList<>(shortest);//this one also didn't work but kept it
        //System.out.println("Bottom - Target " + target + " Cache " + cache[target]);//Debugging

        return shortest;
    }

Answer 1

正如@btilly上面的评论所建议的，我需要这样做，

(cache[target] != null) return cache[target].clone();