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

bestSum - 动态规划

bestSum - Dynamic Programming

algorithm

recursion

dynamic-programming