java - 如何使用内存来提高该算法的运行时间？

Question

问题描述如下:

If we can assign either a positive or negative sign to each integer ina set of integers, how many ways can we sum the signed integers toequal a target value? We must use every integer in the set.

Eg [1, 2, 3, 2], target = 0

Two ways [-1, 2, -3, 2], and [1, -2, 3,-2]

我的解决方案如下(java)

public static void main(String[] args) {
  int[] nums = {1, 2, 3, 2};
  int x = helper(0, 0, nums, 0);
  System.out.println(x);
}

private static int helper(int step, int sumSoFar, int[] nums, int target) {
  if (step == nums.length) {
    return sumSoFar == target ? 1 : 0;
  }

  return
    helper(step + 1, sumSoFar + nums[step], nums, target)
        +
        helper(step + 1, sumSoFar - nums[step], nums, target);
}

我知道暴力解决方案中有很多可能的重复计算，但我不明白传入 sumSoFar 变量是否有效地形成了内存技术？

如果没有，我如何使用内存来提高该算法的运行时性能？

Answer 1

您可以使用 HashMap 通过内存来解决这个问题(例如:Guava Table)

Table<Integer, Integer, Integer> calculated = HashBasedTable.create();

private static int helper(int step, int sumSoFar, int[] nums, int target) {
   if (step == nums.length) {
      return sumSoFar == target ? 1 : 0;
   }

   if (calculated.contains(step, sumSoFar)) {
       return calculated.get(step, sumSoFar)
   }
   int result = helper(step + 1, sumSoFar + nums[step], nums, target)
        +
        helper(step + 1, sumSoFar - nums[step], nums, target);
   calculated.put(step, sumSoFar, result);
   return result;
}