将n个数字加到有限制条件的方法总数

Question

我正努力找到以下问题的DP递归：给定n intervals和k，找出存在从n个给定间隔到k个n个数字（每个间隔一个）求和的可能性。

例如：

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

所以只有一个有效的解决方案（2 + 2）。

有什么建议吗？

Answer 1

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

Let 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)