Количество способов сложить n чисел в k с ограничениями

Question

Я изо всех сил пытаюсь найти рекурсию DP для следующей задачи: Учитывая N intervals of consecutive positive numbers и M, найдите, сколько существует возможностей суммирования n чисел (по одному из каждого интервала) из n заданных интервалов в k.

например:

n = 2, k = 4
where the n intervals are:
[0, 1, 2]
[0, 1, 2]

, поэтому существует только одно допустимое решение (2 + 2).

Я ищу восходящий подход. Вот что я пробовал:

long getPossibilities(int N, int M, vector<vector<int>> &limits) {
vector<vector<long>> dp (N, vector<long>(M + 1, 0));

for(int i = 0; i < N; i++) {
    for(int k = limits[i][0]; k <= limits[i][1]; k++){
        dp[0][k] = 1;
    }
}

for(int i = 1; i < N; i++) {
    for(int j = 1; j <= M; j++) {
        dp[i][j] = dp[i - 1][j];
        for(int k = limits[i][0]; k <= limits[i][1]; k++) {
            if(j - k >= 0) {
                dp[i][j] = (dp[i][j] + dp[i][j - k]) % 1000000007;
            }
        }
    }
}
return dp[N - 1][M];
}

Есть предложения?

Answer 1

Если у вас есть массив A[i][j], представляющий количество способов суммирования до i с первыми j диапазонами, а j+1-й диапазон - от a до b, то у вас есть отношение:

A[i][j+1] = sum(A[x][j] for x = i-a to i-b)

(обработка за пределами читается как 0).

Этот шаг обновления рискует занять время O (M ^ 2), если b-a велико, и это вероятно, почему ваше решение истекло. Вы можете избежать этого, сначала вычислив кумулятивные суммы: пусть B[i][j] = sum(A[i'][j] for i'=0 to i).

Затем A[i][j+1] = B[i-a][j] - B[i-b-1][j] (*)

Процесс будет:

1. начинаться с A[i][0] = 1 если i=0, иначе 1
2. set j=0
3. Вычислить B[i][j] для каждого i от 0 до M путем суммирования элементов A[_][j].
4. Вычислите A[i][j+1] для каждого i от 0 до M, используя уравнение (*).
5. Увеличивайте j до j=n+1.
6. Go вернуться к шагу 3.

Когда вы закончите, A[M][n] будет результатом.

Если вы сообразительны, вы, вероятно, можете использовать один массив размер M вместо двух массивов размером M по n.

Answer 2

Я предполагаю, что все интервальные записи положительны. Один из подходов динамического программирования c заключается в представлении состояния в виде (n, t), где n - индекс текущего интервала, а t - целевая сумма. Например, начальное состояние в вашем примере: n=0 и t=4.

Позвольте f(n, t) обозначить количество способов, которыми мы можем выбрать один элемент от интервала n до последнего сумма выбранных элементов составляет t. Затем в псевдокоде

f(n, t) = sum(f(n+1), t - row[n][j]) for j <= len(row[n]))

Вот одна из возможных реализаций с использованием Python; naive функция` включена для проверки правильности (предполагается, что все интервалы имеют одинаковую длину).

def naive(xs, target):
  from itertools import product
  res = 0
  for tup in product(*xs):
    res += sum(tup) == target
  return res 

def one_per_row_sums(xs, target):
  n = len(xs)
  if n == 0:
    return 0
  m = len(xs[0])
  assert all(len(x) == m for x in xs)

  def f(n, k):
    if k < 0:
      return 0
    if n == 0:
      return sum(1 if x == k else 0 for x in xs[n])
    else:
      return sum(f(n-1, k-j) for j in xs[n])

  return f(n-1, target)

xs = [[0, 1, 2], [0, 1, 2]]
assert naive(xs, 4) == one_per_row_sums(xs, 4)

# larger test
import numpy as np
n = 6
m = 6
xs = np.sort(np.random.randint(0, 10, (n, m)), axis=1)
assert one_per_row_sums(xs, 20) == naive(xs, 20)