0

有 nx 1 的网格。你必须用至少 r 个红色单元格，至少 g 个绿色单元格，至少 b 个蓝色单元格给它上色。(n + r + g <= n)。如果两种模式至少在一个位置不同，则称它们不同。你可以用多少种方式给它上色。（解决方案可以是算法的或数学的）。

我的尝试：

enter code here
int func(int id, int r, int g, int b)
{
     int ma = 0;
     if (id == n) {
        if (r > 0)
            ma++;
        if (g > 0)
             ma++;
        if (b > 0)
             ma++;
        return ma;
     }
     if (r > 0)
       ma += func(r-1, g, b, id + 1);
     if (g > 0)
       ma += func(r, g-1, b, id + 1);
     if (b > 0)
        ma += func(r, g, b-1, id + 1);

    if (r + g + b < n - id)  {
           ma += func(r, g, b, id + 1);
    }

    return ma;

}

4

1 回答 1

0

假设它们的数量是f(n,r,g,b)，那么我们有以下递归：

f(n,r,g,b) = f(n-1,r,g,b)*3 + f(n-1,r-1,g,b)+f(n-1,r,g-1,b)+f(n-1,r,g,b-1).

我们也知道基本情况：f(1,1,0,0)=f(1,0,1,0)=f(1,0,0,1)=1. 从底部开始，通过上面的递归建立 f(n,r,g,b)。（如果您使用记忆而不是 for 循环，这很简单）。运行时间是O(n*r*g*b)。

更新：您的代码接近我的答案，但首先我应该说它是错误的，其次，您使用了导致指数运行时间的朴素递归，分配了一个大小为 n r g*b 的数组，以防止重新计算已经计算的答案。有关记忆的实例，请参见this。

于 2013-10-10T13:48:34.897 回答