分数的方法数

Question

给定一个数字N,打印它可以表示的方式

N = a + b + c + d

同

1 <= a <= b <= c <= d; 1 <= N <= M

我的观察:

For N = 4: Only 1 way - 1 + 1 + 1 + 1

For N = 5: Only 1 way - 1 + 1 + 1 + 2

For N = 6: 2 ways     - 1 + 1 + 1 + 3
                        1 + 1 + 2 + 2

For N = 7: 3 ways     - 1 + 1 + 1 + 4
                        1 + 1 + 2 + 3
                        1 + 2 + 2 + 2

For N = 8: 5 ways     - 1 + 1 + 1 + 5
                        1 + 1 + 2 + 4
                        1 + 1 + 3 + 3
                        1 + 2 + 2 + 3
                        2 + 2 + 2 + 2

So I have reduced it to a DP solution as follows:
 DP[4] = 1, DP[5] = 1;

for(int i = 6; i <= M; i++)
   DP[i] = DP[i-1] + DP[i-2];

我的观察是正确的还是我遗漏了任何东西.我没有任何测试用例可以运行.如果方法正确或错误,请告诉我.

Answer 1

这不对.这是正确的:

让我们DP[n,k]表示数字n总和的方式的k数量.那你在找DP[n,4].

DP[n,1] = 1
DP[n,2] = DP[n-2, 2] + DP[n-1,1] = n / 2
DP[n,3] = DP[n-3, 3] + DP[n-1,2]
DP[n,4] = DP[n-4, 4] + DP[n-1,3]

我只会解释最后一行,你可以马上看到,为什么其他人都是真的.

我们来看一个例子吧n=a+b+c+d.

如果a> 1,n-4 = (a-1)+(b-1)+(c-1)+(d-1)则为有效总和DP[n-4,4].

如果a = 1,那么n-1 = b+c+d是有效的总和DP[n-1,3].

也相反:

对于每个有效,n-4 = x+y+z+t我们有效n=(x+1)+(y+1)+(z+1)+(t+1).

对于每个有效,n-1 = x+y+z我们有效n=1+x+y+z.