bestSum -动态规划

Question

我正试图解决bestSum问题，该问题基本上找到了添加到目标值的最小元素量，以下似乎工作良好，

示例输出，bestSum(10, new int[]{1,2,5})应该返回[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版本时，我遇到了一个问题，我注意到当我打印缓存时，打印有一个"顶部"，正在添加一个额外的元素，我不知道为什么，我做错了什么?

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();