Количество способов окрашивания сетки

Question

Существует сетка n x 1. Вы должны покрасить ее по крайней мере красные клетки, по крайней мере, зеленые клетки, по крайней мере, в синие клетки. (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; 

}

Answer 1

Пусть число из них является 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). (Простой, если вы используете memoization вместо циклов). время работы O(n*r*g*b).

Update: Ваш код близок к моему ответу, но сначала я должен сказать, что это не так, во-вторых, вы использовали наивную рекурсию, которая вызывает к экспоненциальному времени работы, выделить массив размера п г г * б, для предотвращения повторного вычисления уже вычисленного ответа. См. this для экземпляра memoization.