5

这是标记为动态规划的问题（给定一个数字 N，找到将其写为两个或多个连续整数之和的方法数）和示例 15 = 7+8, 1+2+3+4+ 5、4+5+6

我用这样的数学解决了：

a + (a + 1) + (a + 2) + (a + 3) + ... + (a + k) = N

(k + 1)*a + (1 + 2 + 3 + ... + k) = N

(k + 1) a + k (k+1)/2 = N

(k + 1)*(2*a + k)/2 = N

然后检查如果 N 可被 (k+1) 和 (2*a+k) 整除，那么我可以在 O(sqrt(N)) 时间内找到答案

这是我的问题，你如何通过动态编程来解决这个问题？什么是复杂度（O）？

PS：对不起，如果这是一个重复的问题。我搜索但我能找到

4

6 回答 6

3

公认的答案很好，但没有明确提出更好的方法。如下发布我的java代码以供参考。它可能非常冗长，但更清楚地解释了这个想法。这假设连续整数都是正数。

private static int count(int n) {
    int i = 1, j = 1, count = 0, sum = 1; 
    while (j<n) {
        if (sum == n) { // matched, move sub-array section forward by 1
            count++; 
            sum -= i; 
            i++;
            j++;
            sum +=j; 
        } else if (sum < n) { // not matched yet, extend sub-array at end
            j++; 
            sum += j; 
        } else { // exceeded, reduce sub-array at start
            sum -= i; 
            i++; 
        }
    }
    return count;
}
于 2018-07-01T16:45:14.920 回答
1

对于奇数N，这个问题相当于找到 N 的除数不超过sqrt(N)。（即使是N，也有一些曲折。）O(sqrt(N)/ln(N))如果您可以访问素数列表，则该任务需要完成，O(sqrt(N))否则。

我看不出动态编程在这里有什么帮助。

于 2010-12-27T07:48:31.423 回答
1

我们可以使用动态规划来计算所有 K 到 N 的 1+2+3+...+Ksum[i]的总和。下面表示总和 1+2+3+...+i。

sum = [0]
for i in 1..N:
  append sum[i-1] + i to sum

有了这些和，我们可以快速找到所有和为 N 的连续整数序列。和 i+(i+1)+(i+2)+...j 等于sum[j] - sum[i] + 1。如果总和小于 N，我们增加j。如果总和大于 N，我们增加i。如果总和等于 N，我们增加我们的计数器和i两者j。

i = 0
j = 0
count = 0
while j <= N:
  cur_sum = sum[j] - sum[i] + 1
  if cur_sum == N:
    count++
  if cur_sum <= N:
    j++
  if cur_sum >= N:
    i++

虽然有比使用这种动态编程解决方案更好的选择。该sum数组可以使用公式 k(k+1)/2 进行数学计算，因此我们可以即时计算它而无需额外的存储空间。更好的是，由于我们在每次迭代中只将我们正在处理的和的端点最多移动 1，因此我们可以通过添加/减去添加/删除的值来更有效地计算它。

i = 0
j = 0
sum = 0
count = 0
while j <= N:
  cur_sum = sum[j] - sum[i] + 1
  if cur_sum == N:
    count++
  if cur_sum <= N:
    j++
    sum += j
  if cur_sum >= N:
    sum -= i
    i++
于 2010-12-27T12:23:50.653 回答
0

为了解决这个问题，我们将尝试 [1, M] 中所有连续整数的和，其中 M 由 M(M+1)/2 = N 导出。

int count = 0
for i in [1,M]
  for j in [i, M]
    s = sum(i, j) // s = i + (i+1) + ... + (j-1) + j
    if s == N 
       count++
    if s >= N
       break
return count

由于我们不想sum(i, j)在每次迭代中从头开始计算，我们将使用一种称为“memoization”的技术。让我们创建一个整数矩阵sum[M+1][M+1]并设置sum[i][j]为 i + (i+1) + ... + (j-1) + j。

for i in [1, M]
  sum[i][i] = i



int count = 0
for i in [1, M]
  for j in [i + 1, M]
    sum[i][j] = sum[i][j-1] + j
    if sum[i][j] == N
      count++
    if sum[i][j] >= N
      break
return count

复杂度显然是O(M^2)，即O(N)

于 2010-12-27T11:31:36.473 回答
0

1)对于 n >= 0 一个整数，从 0 到 n 的整数之和为 n*(n+1)/2。这是经典的：先这样写这个总和：S = 0 + 1 + ... + n 然后这样： S = n + (n-1) + ... + 0 你看到 2*S 是相等的到 (0+n) + (1 + n-1)) + ... + (n+0) = (n+1) n，所以确实 S = n (n+1)/2。（众所周知，但我更喜欢我的回答是独立的）。

2)从 1 开始，如果我们注意到 cons(m,n) 和 m+(m+1)+...(n-1)+n 正数（即 >=0）之间的整数的连续和，使得 1 <=m<=n 我们看到： cons(m,n) = (0+1+...+n) - (0+1+...+(m-1)) 从 1 给出： cons (m,n) = n*(n+1)/ - m(m-1)/2

3)然后将问题重新转换为以下内容：我们可以用多少种方式将 N 写成 N = cons(m,n) 和 m,n 整数，使得 1<=m<=n ？如果我们有 N = cons(m,n)，这等价于 m^2 - m + (2N -n^2 -n) = 0，即实数多项式 T^2 - m + (2N -n ^2 -n) 有一个实根 m ：它的判别式 delta 必须是一个正方形。但我们有：

delta = 1 - 3*(2*N - n^2 - n)

这个增量是一个整数，必须是一个正方形。因此存在一个整数 M 使得 ：

delta = 1 - 3*(2*N - n^2 - n) = M^2

那是

M^2 = 1 - 6*N + n(n+1)

n(n+1) 总是可以被 2 整除（例如从一开始就是 S 的 2 倍，但这里有一个更微不足道的原因，在连续整数中，一个必须是偶数），因此 M^2 是奇数，这意味着M 一定是奇数。

4)将之前的等式改写为：

n^2 + n + (1-6*N - M^2) = 0

这表明实数多项式 X^2 + X + (1-6*N - M^2) 具有实数零 n ：因此其判别式 gamma 必须是平方，但是：

gamma = 1 - 4*(1-6*N-M^2)

这必须是一个正方形，所以这里又存在一个整数 G 使得

G^2 = 1 - 4*(1-6*N-M^2)

G^2 = 1 + 4*(2*N + m*(m-1))

这表明，由于 M 是奇数，G 也是奇数。

5)将 M^2 = 1 - 4*(2*N - n*(n+1)) 减去 G^2 = 1 + 4*(2*N + m*(m-1))) 得到：

G^2 - M^2 = 4*(2*N + m*(m-1)) + 4*(2*N -n*(n+1))
          = 16*N + 4*( m*(m-1) - n*(n+1) )
          = 16*N - 8*N (because N = cons(m,n))
          = 8*N

最后这可以重写为：

(G-M)*(G+M) = 8*N, that is

[(G-M)/2]*[(G+M)/2] = 2*N

其中 (GM)/2 和 (G+M)/2 是整数（GM 和 G+M 是偶数，因为 G 和 M 是奇数）

6)因此，在将 N 写为 cons(m,n) 的每种方式中，我们都可以将一种方式（并且只有一种方式，因为 M 和 G 是唯一确定的）将 2*N 分解为乘积 x*y，其中x = (GM)/2 和 y = (G+M)/2 其中 G 和 M 是两个奇数。由于 G = x + y 和 M = -x + y，因为 G 和 M 是奇数，我们看到 x 和 y 应该具有相反的奇偶性。因此，在 x 和 y 中，一个是偶数，另一个是奇数。因此 2*N = x*y 在 x 和 y 中，一个是偶数，另一个是奇数。令 c 为 x 和 y 中的奇数，d 为偶数。然后 2*N = c*d，因此 N = c*(d/2)。所以 c 是奇数除以 N，并且由 N 唯一确定，只要 N = cons(m,n)。反过来，只要 N 有一个奇数除数，就可以对所有这些东西进行逆向工程以找到 n 和 m。

7) *结论：N = cons(m,n) 的写法数（如我们所见，N 写成连续整数之和的写法数）和N 的奇数除数。 *

8)最后，我们要找的数是 n 的奇数除数。我猜想通过 DP 或其他方式解决这个问题比解决前一个问题更容易。

于 2013-09-17T17:50:08.660 回答
0

当你认为它颠倒时（斯威夫特）......

func cal(num : Int) -> Int {
 let halfVal = Double(Double(num)/2.0).rounded(.up)
 let endval = Int((halfVal/2).rounded(.down))
 let halfInt : Int = Int(halfVal)

 for obj in (endval...halfInt).reversed() {
     var sum : Int = 0
     for subVal in (1...obj).reversed() {
         sum = sum + subVal
         if sum > num {
             break
         }
         if sum == num {
             noInt += 1
             break
         }
     }
 }
 return noInt
}
于 2021-11-14T03:42:21.090 回答