algorithm - 将数字表示为四个正整数之和 1<a<=b<=c<=d

Question

给定 N=a+b+c+d，其中 a、b、c、d 是大于 0 的正整数且 a<=b<=c<=d。

我们必须计算将 N 表示为 4 个这样的数字之和的方式的数量。

我的方法是有四个循环并将它们添加到 n 。 但是时间复杂度是 O(n^4) 我们可以减少它吗？

Answer 1

提示:

1. 有多少种方法可以将 N 表示为两个数字 a 和 b 的和？将此称为 S2(N)。

2. 你能算出有多少种方法可以将 N 表示为三个数字 a、b 和 c 的和吗？ (在你的答案中使用 S2())？称之为 S3(N)。

   从考虑S3(100)开始，统计最大数(c)为97的可能性；然后计算 96、95 等的可能性。这适用于 c>50，但由于重复计算某些可能性而失效。您能否通过向 S2() 和 S3() 添加一个参数来控制总和中的最大数来解决此问题？

3. 现在，有多少种方法可以将 N 表示为四个数字 a、b、c 和 d 的和？ (在你的答案中使用 S3())。