如何使用记忆来提高该算法的运行时间

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

您可以使用哈希图通过记忆(例如：Guava表(来解决此问题

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

Answer 2

您可能希望使用以下算法实现"记忆化"。我在递归中又添加了一个参数——rest，它可以是不可见元素的绝对正和或绝对负和。因此，如果没有机会达到目标，它就会破坏递归。

使用这种方法，最坏的情况仍然是O(2^n(-即[0,0,0]，但在实践中它更快。

注意：假设nums中的元素是正的，如果不是，则可以在O(n(中生成它们。

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

private static int helper(int step, int sumSoFar, int[] nums, int target, int rest) {
if (step == nums.length-1) {
return sumSoFar == target ? 1 : 0;
}
int nextStep = step+1;
int nextSumPos = sumSoFar + nums[nextStep];
int nextSumNeg = sumSoFar - nums[nextStep];
int nextRest = rest - nums[nextStep];
boolean pos = false;
if ((nextSumPos > target && nextSumPos - nextRest > target) ||  
(nextSumPos < target && nextSumPos + nextRest < target)) { /* do nothing */  }
else { pos = true; }
boolean neg = false;
if ((nextSumNeg > target && nextSumNeg - nextRest > target) ||
(nextSumNeg < target && nextSumNeg + nextRest < target)) { /* do nothing */ }
else { neg = true; }
if (pos && neg) {
return helper(nextStep, nextSumPos, nums, target, nextRest)
+  helper(nextStep, nextSumNeg, nums, target, nextRest);
}else if (pos && !neg) {
return helper(nextStep, nextSumPos, nums, target, nextRest);
} else if (!pos && neg) {
return helper(nextStep, nextSumNeg, nums, target, nextRest);
} else { /* !pos && !neg */
return 0;
}
}
private static int arraySum(int[] nums) {
int sum = 0;
for (int i = 0; i < nums.length; i++) {
sum += nums[i];
}
return sum;
}