BestSum记忆化java

Question

我有一个函数，它接收一个目标和一个数字数组，目标是返回使用较少的数组数字来实现目标的组合。示例：

sum(8, [1,4,5]) should return [4,4]  
sum(7, [5,3,4,7]) should return [7]`  
sum(8, [2,3,5]) should return [3,5]  
sum(100, [1,2,5,25]) should return [25, 25, 25, 25]  

在我尝试执行memoization之前，函数运行得很好……下面是我的代码：

import java.util.ArrayList;

public class BestSum {
    ArrayList<Integer> memoInt;
    ArrayList<ArrayList<Integer>> memoList;
    BestSum () {
        memoList = new ArrayList<ArrayList<Integer>>();
        memoInt = new ArrayList<Integer>();
    }
    public ArrayList<Integer> sum (int target, int nums[]) {
        for(int i = 0; i < memoInt.size(); i++) {
            if(memoInt.get(i) == target) {
                return memoList.get(i);
            }
        }
        if(target == 0) {
            return new ArrayList<Integer>();
        }
        if(target < 0) {
            return null;
        }
        ArrayList<Integer> shortestCombination = null;

        for(int i  = 0; i < nums.length; i++) {
            int rest = target-nums[i];
            ArrayList<Integer> currentCombination = sum(rest, nums);
            if(currentCombination != null) {
                currentCombination.add(nums[i]);
                if(shortestCombination == null || currentCombination.size() < shortestCombination.size()){
                    shortestCombination = new ArrayList<Integer>();
                    shortestCombination = (ArrayList)currentCombination.clone();
                }
            }
        }
        memoInt.add(target);
        memoList.add(shortestCombination);
        return shortestCombination;
    }
    public static void main(String[] args) {
        int target = 8;
        int nums[] = {1,4,5};
        BestSum bs = new BestSum();
        System.out.println(bs.sum(target, nums).toString()); //[4,4]
    }
}

然而，当我运行这个而不是4，4时，我得到4,1,4...有什么建议吗？

Answer 1

好的，我修复了代码:D

import java.util.ArrayList;
import java.util.*;

public class BestSum {
    HashMap<Integer, ArrayList<Integer>> hp;
    BestSum () {
       hp = new HashMap<Integer, ArrayList<Integer>>();
    }
    public ArrayList<Integer> sum (int target, int nums[]) {
        if(hp.containsKey(target)) {
            return hp.get(target);
        }
        if(target == 0) {
            return new ArrayList<Integer>();
        }
        if(target < 0) {
            return null;
        }
        ArrayList<Integer> shortestCombination = null;

        for(int i  = 0; i < nums.length; i++) {
            int rest = target-nums[i];
            ArrayList<Integer> currentCombination = sum(rest, nums);
            if(currentCombination != null) {
                ArrayList<Integer> combination = new ArrayList<Integer>();
                combination = (ArrayList)currentCombination.clone();
                combination.add(nums[i]);
                if(shortestCombination == null || combination.size() < shortestCombination.size()){
                    shortestCombination = new ArrayList<Integer>();
                    shortestCombination = (ArrayList)combination.clone();
                }
            }
        }
       
        hp.put(target, shortestCombination);
        return shortestCombination;
    }
    public static void main(String[] args) {
        int target = 8;
        int nums[] = {1,4,5};
        BestSum bs = new BestSum();
        System.out.println(bs.sum(target, nums).toString()); //[4,4]
    }
}

Answer 2

稍微调整了for循环，

for(int i  = 0; i < nums.length; i++) {
   int rest = target-nums[i];
   ArrayList<Integer> currentCombination = sum(rest, nums);
   if(currentCombination != null) {
        ArrayList<Integer> tempCombination = new ArrayList<>(currentCombination);
        tempCombination.add(nums[i]);
        if(shortestCombination == null || tempCombination.size() < shortestCombination.size()){
            shortestCombination = tempCombination;
        }
    }
}

这是一个重要的步骤，因为之前的内存正在被重新分配，因此所有的旧值都是预先存储的，这导致了问题。我是在调试的时候发现的。在使用递归技术时，分配一个新的列表总是一个好主意。