我如何使用备忘录来改善该算法的运行时间？

Question

指出问题：

如果我们可以为正整数中的每个整数分配正号或负号一组整数，我们可以通过多种方式将有符号整数求和为等于目标值？我们必须使用集合中的每个整数。

例如[1,2,3,2]，目标= 0

[两种方式[-1、2，-3、2]和[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

您可以使用哈希图通过记忆解决此问题（例如：番石榴表）

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;
}