Как я могу использовать памятку, чтобы улучшить время выполнения этого алгоритма?

Question

Задача сформулирована так:

Если мы можем назначить положительный или отрицательный знак каждому целому числу в наборе целых чисел, сколько способов мы можем суммировать целые числа со знаком в целевое значение? ? Мы должны использовать каждое целое число в наборе.

Например, [1, 2, 3, 2], target = 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

Возможно, вы хотите добиться «запоминания» с помощью следующего алгоритма. Я добавил еще один параметр в рекурсии - rest, который может быть абсолютной положительной или абсолютной отрицательной суммой невидимых элементов. Таким образом, он нарушает рекурсию, если нет шансов достичь цели.

При таком подходе наихудшим случаем по-прежнему является O (2 ^ n) - т.е. [0,0,0,0], но на практике это происходит быстрее.

Примечание: предполагается, что элементы в числах положительны, если вы не можете сделать их в 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;
}

Answer 2

Вы можете использовать карту ha sh для решения этой проблемы с запоминанием (напр., Таблица 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;
}