Programação dinâmica - Problema "Parquet"

Problemas comuns resolvidos usando DP incluem:

Problema "Parquet"

Descrição

Dado um grid de tamanho $N \times M$. Encontre o número de maneiras para preencher o grid com "figuras" de tamanho $2 \times 1$ (nenhuma célula deve ser deixada vazia e as figuras não devem se sobrepor).

Deixe que o estado da DP seja: D[i][mask], onde i = 1 ... N, e mask = 0 ... 2^M-1. i representa o número de linhas no grid atual e mask é o estado da última linha do grid atual. Se o j-ésimo bit de mask for 0 a célula correspondente será preenchida, caso contrário, não será preenchida. Claramente, a resposta para o problema será D[N][0].

Nós estaremos construindo o estado da DP iterando sobre cada i = 1 ... N e cada mask = 0 ... 2^M-1, e para cada mask estaremos apenas fazendo a transição adiante, ou seja, estaremos adicionando figuras para o grid atual.

Implementação

int n, m;
vector < vector<long long> > d;


void calc (int x = 0, int y = 0, int mask = 0, int next_mask = 0)
{
    if (x == n)
        return;
    if (y >= m)
        d[x+1][next_mask] += d[x][mask];
    else
    {
        int my_mask = 1 << y;
        if (mask & my_mask)
            calc (x, y+1, mask, next_mask);
        else
        {
            calc (x, y+1, mask, next_mask | my_mask);
            if (y+1 < m && ! (mask & my_mask) && ! (mask & (my_mask << 1)))
                calc (x, y+2, mask, next_mask);
        }
    }
}


int main()
{
    cin >> n >> m;

    d.resize (n+1, vector<long long> (1<<m));
    d[0][0] = 1;
    for (int x=0; x<n; ++x)
        for (int mask=0; mask<(1<<m); ++mask)
            calc (x, 0, mask, 0);

    cout << d[n][0];

}