algorithm - 避免暴力破解: Counting Solutions

Question

在一次编程竞赛中，存在一个问题:

Count all solutions to the equation: x + 4y + 4z = n. You will be given n and you will determine the count of solutions. Assume x, y and z are positive integers.

我考虑过使用三重for循环(暴力)，但效率低下，导致TIME LIMIT EXCEED。 (因为 n 可能 = 1000,000):

int sol = 0;
for (int i = 1; i <= n; i++)
{
 for (int j = 1; j <= n / 4; j++)
 {
  for (int k = 1; k <= n / 4; k++)
   {
      if (i + 4 * j + 4 * k == n)
         sol++;
   }
 }
}

我的 friend 可以解决这个问题。当我问他时，他说他根本没有使用暴力。相反，他将方程转换为“级数”(即峰会)。我让他告诉我怎么做，但他拒绝了:)

我可以知道怎么做吗？

Answer 1

这是 coin change problem 的特例，一般通过动态规划来解决。

但是在这里我们可以阐述简单的解决方案。我认为 x,y,z > 0

x + 4*(y+z)=n 设 y + z = q = p + 1 (q > 1, p > 0)

x+4*q=n

x+4*p=n-4

x 和 p 有 M = Floor((n-5)/4) 变体，因此有 M 个可能的值 q = 2..M+1 对于每个 q>1，y 和 z 有 (q-1) 个变体:q = 1 + (q-1) = 2 + (q-2) +..+(q-1)+1

所以我们有 N=1 + 2 + 3 + ... + M = M * (M + 1)/2 个解决方案

示例:

n = 15；

M = (15 - 5) div 4 = 2

N = 3

(3,1,2),(3,2,1),(7,1,1)