给定数字N，找到将其写为两个或多个连续整数之和的方式数量 [英] Given a number N, find the number of ways to write it as a sum of two or more consecutive integers

问题描述

以下是问题，已将其标记为动态编程（给出了N，找到将其写为两个或多个连续整数之和的方式数），例如15 = 7 + 8，1 + 2 + 3 + 4 + 5，4 + 5 + 6

Here is the problem that tagged as dynamic-programming (Given a number N, find the number of ways to write it as a sum of two or more consecutive integers) and example 15 = 7+8, 1+2+3+4+5, 4+5+6

我用这样的数学方法求解：

I solved with math like that :

a +（a + 1）+（a + 2）+（a + 3） + ... +（a + k）= N

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

（k + 1）* a +（1 + 2 + 3 + ... + k ）= N

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

（k + 1） a + k （k + 1）/ 2 = 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））时间找到答案

Then check that if N divisible by (k+1) and (2*a+k) then I can find answer in O(sqrt(N)) time

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

Here is my question how can you solve this by dynamic-programming ? and what is the complexity (O) ?

P.S：对不起，如果是重复的问题。我搜索了但可以找到

P.S : excuse me, if it is a duplicate question. I searched but I can find

推荐答案

我们可以使用动态编程来计算1 + 2 + 3 +的总和。对于不超过N的所有K，为+ K。下面的 sum [i] 表示总和1 + 2 + 3 + ... + i。

We can use dynamic programming to calculate the sums of 1+2+3+...+K for all K up to N. sum[i] below represents the sum 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 。

With these sums we can quickly find all sequences of consecutive integers summing to N. The sum i+(i+1)+(i+2)+...j is equal to sum[j] - sum[i] + 1. If the sum is less than N, we increment j. If the sum is greater than N, we increment i. If the sum is equal to N, we increment our counter and both i and 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个，因此我们可以通过添加/减去相加/相减后的值来更有效地计算它。 / p>

There are better alternatives than using this dynamic programming solution though. The sum array can be calculated mathematically using the formula k(k+1)/2, so we could calculate it on-the-fly without need for the additional storage. Even better though, since we only ever shift the end-points of the sum we're working with by at most 1 in each iteration, we can calculate it even more efficiently on the fly by adding/subtracting the added/removed values.

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++

这篇关于给定数字N，找到将其写为两个或多个连续整数之和的方式数量的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！