DP sobre perfil roto

Recursos

La DP sobre perfil roto (broken profile DP) es un subconjunto de la DP con máscaras de bits. Los problemas de esta categoría suelen tener las siguientes propiedades:

1. Tratan de rellenar una grilla 2D.
2. Una de las dimensiones es mucho más chica que la otra.
3. Al rellenar la grilla, cada celda depende solo de celdas adyacentes.
4. Las celdas no tienen muchos valores posibles (usualmente solo 2).

La tercera propiedad es especialmente importante, porque significa que podemos procesar las celdas columna por columna (imaginar una serpiente envolviendo la grilla). Entonces solo nos importa la celda procesada más a la derecha en cada fila (de ahí el nombre “perfil roto”).

La cuarta propiedad sugiere que deberíamos usar una máscara de bits para representar ese perfil roto.

Tutorial

Procesaremos las celdas de la grilla columna por columna, fila por fila. Sean $i$ y $j$ la fila y la columna de la celda actual que estamos considerando, y $\texttt{dp}[i][j][mask]$ el número de formas de teselar la grilla de modo que:

• Todas las celdas desde la celda $(0, 0)$ hasta la celda $(i, j - 1)$ están cubiertas.
• Todas las celdas desde la celda $(i + 1, j)$ hasta la celda $(N - 1, M - 1)$ están vacías.
• $mask$ representa si cada una de las $N$ celdas restantes está vacía, con el $k$-ésimo bit correspondiendo a la celda de la fila $k$.

Por ejemplo, el siguiente estado contribuiría a $\texttt{dp}[1][3][00101_2]$:

La respuesta será $\texttt{dp}[N - 1][M - 1][0]$.

Ahora tenemos tres casos al calcular $\texttt{dp}[i][j][mask]$:

• El $i$-ésimo bit de la máscara es 0, lo que significa que la celda $(i, j)$ está cubierta.
  • Caso 1: usamos una loseta horizontal para cubrirla.
    • La celda $(i, j - 1)$ debió estar vacía, así que hay $\texttt{dp}[i - 1][j][mask \oplus 2^i]$ formas de hacer esto.
  • Caso 2: usamos una loseta vertical para cubrirla.
    • Esto solo es posible si $i > 0$.
    • La celda $(i,j-1)$ debió estar cubierta y la celda $(i-1,j)$ debió estar vacía, así que hay $\texttt{dp}[i - 1][j][mask \oplus 2^{i - 1}]$ formas de hacer esto.
    • Esto corresponde a if (i && !(mask & (1 << i)) && !(mask & (1 << i - 1))) en el código de abajo.
• El $i$-ésimo bit de la máscara es 1, lo que significa que la celda $(i, j)$ está vacía.
  • La celda $(i, j - 1)$ debió estar cubierta, así que hay $\texttt{dp}[i - 1][j][mask \oplus 2^i]$ formas de hacer esto.
    • Esto es lo mismo que el caso 1 de cuando el $i$-ésimo bit de la máscara es 0, así que los manejamos simultáneamente en el código de abajo.

Observar que los índices que necesitamos usar pueden volverse negativos y por lo tanto requerirán wrapping. Para simplificar los cálculos y evitar esto, simplemente descartamos las primeras dos dimensiones del arreglo de DP, ya que $\texttt{dp}[i][j]$ depende solo de $\texttt{dp}[i - 1][j]$.

Implementación

Complejidad temporal: $\mathcal O(NM 2^N)$

#include <bits/stdc++.h>
using namespace std;
 
const int MOD = 1e9 + 7;
 
int dp[1 << 10][2];
 
int main() {
	int n, m;
	cin >> n >> m;
	dp[0][0] = 1;
	for (int j = 0; j < m; j++)
		for (int i = 0; i < n; i++) {
			for (int mask = 0; mask < (1 << n); mask++) {
				dp[mask][1] = dp[mask ^ (1 << i)][0];  // Horizontal or no tile
				if (i && !(mask & (1 << i)) && !(mask & (1 << i - 1)))  // Vertical tile
					dp[mask][1] += dp[mask ^ (1 << i - 1)][0];
				if (dp[mask][1] >= MOD) dp[mask][1] -= MOD;
			}
			for (int mask = 0; mask < (1 << n); mask++) dp[mask][0] = dp[mask][1];
		}
	cout << dp[0][0] << '\n';
}

import java.util.*;
 
public class Main {
	static final int MOD = 1_000_000_007;
 
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt(), m = sc.nextInt();
 
		int[][] dp = new int[1 << n][2];
		dp[0][0] = 1;
 
		for (int j = 0; j < m; j++)
			for (int i = 0; i < n; i++) {
				for (int mask = 0; mask < (1 << n); mask++) {
					dp[mask][1] = dp[mask ^ (1 << i)][0];
					if (i > 0 && (mask & (1 << i)) == 0 && (mask & (1 << (i - 1))) == 0)
						dp[mask][1] += dp[mask ^ (1 << (i - 1))][0];
					if (dp[mask][1] >= MOD) dp[mask][1] -= MOD;
				}
				for (int mask = 0; mask < (1 << n); mask++) dp[mask][0] = dp[mask][1];
			}
 
		System.out.println(dp[0][0]);
	}
}

import sys
 
input = sys.stdin.readline
 
MOD = 10**9 + 7
 
n, m = map(int, input().split())
 
dp = [[0] * 2 for _ in range(1 << n)]
dp[0][0] = 1
 
for j in range(m):
	for i in range(n):
		for mask in range(1 << n):
			dp[mask][1] = dp[mask ^ (1 << i)][0]
			if i > 0 and not (mask & (1 << i)) and not (mask & (1 << (i - 1))):
				dp[mask][1] += dp[mask ^ (1 << (i - 1))][0]
			if dp[mask][1] >= MOD:
				dp[mask][1] -= MOD
		for mask in range(1 << n):
			dp[mask][0] = dp[mask][1]
 
print(dp[0][0])

Problemas