数的除法

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

我认为函数 f(N,m,n) 的定义，其中 N 是我们想要产生的总和，m 是总和中每一项的最大值，n 是其中的项数总和应该有效。

f(N,m,n) 定义为 n=1 如果 N > m 则为 0，否则为 N。

对于 n > 1，f(N,m,n) = 总和，对于 f(S-t, t, n-1) 从 1 到 N 的所有 t

这表示设置每一项，从右到左。

然后您可以使用此关系解决问题，可能使用记忆。

对于最大 n=4 和 N=5000，（并巧妙地实施以在存在 0 种可能性时快速计算），我认为这对于大多数目的来说可能足够快地计算出来。

Answer 2

不幸的是，你的递归是错误的，因为对于 n = 9，解是 6，而不是 8。

如果 p(n,k) 是将 n 分成 k 个非零整数部分的方法数，那么我们有

p(0,0) = 1
p(n,k) = 0 if k > n or (n > 0 and k = 0)
p(n,k) = p(n-k, k) + p(n-1, k-1)

因为要么有一个值为 1 的分区（在这种情况下，将这部分去掉会产生一个 n-1 的分区为 k-1 个部分），要么你可以从每个分区中减去 1，得到一个 n - k.很容易证明这个过程是双射的，因此是递归的。

更新：

对于特定情况 k = 4，OEIS 告诉我们存在另一种仅依赖于 n 的线性递归：

a(n) = 1 + a(n-2) + a(n-3) + a(n-4) - a(n-5) - a(n-6) - a(n-7) + a(n-9)

这个递归可以通过标准方法求解得到一个明确的公式。我写了一个小SAGE script来解决它，得到了以下公式：

a(n) = 1/144*n^3 + 1/32*(-1)^n*n + 1/48*n^2 - 1/54*(1/2*I*sqrt(3) - 1/2)^n*(I*sqrt(3) + 3) - 1/54*(-1/2*I*sqrt(3) - 1/2)^n*(-I*sqrt(3) + 3) + 1/16*I^n + 1/16*(-I)^n + 1/32*(-1)^n - 1/32*n - 13/288

OEIS 也 gives the following simplification:

a(n) = round((n^3 + 3*n^2 -9*n*(n % 2))/144)

我还没有验证。

Answer 3

这是不正确的。这是正确的：

设 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。

Answer 4

#include <iostream>

using namespace std;

int func_count( int n, int m )
{

     if(n==m)
        return 1;
     if(n<m)
        return 0;
     if ( m == 1 )
        return 1;
     if ( m==2 )
        return (func_count(n-2,2) + func_count(n - 1, 1));
     if ( m==3 )
        return (func_count(n-3,3) + func_count(n - 1, 2));

     return (func_count(n-1, 3) + func_count(n - 4, 4));
}

int main()
{

     int t;
     cin>>t;
     cout<<func_count(t,4);
     return 0;
}

数的除法

Number of ways to divide a number

algorithm

numbers

dynamic-programming