algorithm - N 个相同的球在 A 个不同的盒子中的组合

Question

int f(int n,int a,int x)
{
        if(a==1)
        {
            if(n>=0 && n<=x)  //HERE WAS ERROR,sorry
                return 1;
            else 
                return 0;
        }

        int ans=0;

        for(int i=0;i<=x;i++)
            ans += f(n-i,a-1,x);

    return ans;
}

您好!

例子:

这是算法，但是它花费了很多时间。 也许您知道解决此问题的更快方法？非常感谢，抱歉让您担心。

Answer 1

你需要的是动态规划。您需要记住函数 f 对于那些已经计算过的参数的值。它也可以像这样在没有递归的情况下实现:

int f(int n,int a,int x)
{
    int q[1000][50]; // to simplify and not use dynamic allocation assume that a < 50 and n < 1000

    q[0][0] = 1;
    for (int i = 1; i < 1000; ++i)
        q[i][0] = 0;

    for (int i = 1; i <= a; ++i)
    {
        for (int j = 0; j <= n; j++)
        {
            int t = 0;
            for (int l = 0; l <= j && l <= x; ++l)
                t += q[j - l][i-1];
            q[j][i] = t;
        }
    }

    return q[n][a];
}

这只是简单的技术演示。可以再优化一次，可以预先计算t-sum，消除l的循环。而且你不必存储整个表 q，你只需要两层，它会减少内存使用。所以结果将如下所示:

int f(int n,int a,int x)
{
    int q[1000][2]; // to simplify and not use dynamic allocation assume n < 1000

    q[0][0] = 1;
    for (int i = 1; i < 1000; ++i)
        q[i][0] = 0;

    int current = 1;
    for (int i = 1; i <= a; ++i)
    {
        int t = 0;
        for (int j = 0; j <= n; j++)
        {
            t += q[j][1 - current];
            if (j > x)
                t -= q[j - x - 1][1 - current];

            q[j][current] = t;
        }
        current = 1 - current;
    }

    return q[n][1 - current];
}

所以最终需要 O(a*n) 的时间来计算。

PS:请注意，answer 可以是一个巨大的数字，它可以溢出任何原生整数类型。