有限制地将n个数和为k的方法的数目

Question

对于以下问题，我很难找到一个DP递归:给定N intervals of consecutive positive numbers和M，找出从n个给定区间到k的n个数之和的可能性(每个区间一个)。

例如：

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]表示用第一个j范围求和到i的方法的数量，而j+1st范围是从a到b的，那么您就有了这样的关系：

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

(将越界读取为0)。

如果b-a很大，此更新步骤可能会占用O(M^2)时间，这也可能是解决方案超时的原因。您可以通过先计算累积和来避免这种情况:让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

• set j=0

• Compute

• 从A[i][0] = 1 if i=0开始，否则，通过使用(*).

• Increment j方程(*).

• Incrementj对每个i从0到M的j=n+1.

• Go A[i][j+1]元素进行求和，直到j=n+1.

• Go返回到步骤3为止。H 235G 236

当您完成时，A[M][n]就是结果。

如果您很聪明，那么您可能可以使用一个大小为M的数组，而不是n使用的两个大小为M的数组。

Answer 2

我假设所有的区间条目都是正的。一种动态规划方法是将状态表示为(n, t)，其中n是当前区间的索引，t是目标和。例如，示例中的初始状态是n=0和t=4。

让f(n, t)表示我们可以从区间n中选择一个元素直到最后一个s.t的方式的数目。所选元素之和为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)