Caminos en grillas

Tutorial

Un arquetipo habitual de problemas de DP involucra una grilla 2D de celdas cuadradas (como papel cuadriculado), y hay que analizar “caminos”. Un camino es una secuencia de celdas cuyo movimiento está restringido a una dirección en el eje $x$ y una dirección en el eje $y$ (por ejemplo, solo se puede mover hacia abajo o hacia la derecha). Por lo general, el camino también tiene que empezar en una esquina de la grilla y terminar en otra. El problema puede pedir contar la cantidad de caminos que satisfacen alguna propiedad, o hallar el máximo / mínimo de alguna cantidad sobre todos los caminos.

Suele ocurrir que los subproblemas de este tipo de DP son un subrectángulo de la grilla completa. Por ejemplo, consideremos un problema en el que contamos la cantidad de caminos de $(1, 1)$ a $(N, M)$ cuando solo podemos movernos en la dirección positiva de $x$ y en la dirección positiva de $y$.

Sea $\texttt{dp}[x][y]$ la cantidad de caminos en el subrectángulo cuyos vértices son $(1, 1)$ y $(x, y)$. Sabemos que la primera celda de un camino contado por $\texttt{dp}[x][y]$ es $(1, 1)$, y que la última celda es $(x, y)$. Sin embargo, la penúltima celda puede ser $(x-1, y)$ o $(x, y-1)$. Así, si fingimos agregar la celda $(x, y)$ a los caminos que terminan en $(x-1, y)$ o en $(x, y-1)$, construimos caminos que terminan en $(x, y)$. Trabajar hacia atrás de esa forma motiva la siguiente recurrencia: $\texttt{dp}[x][y] = \texttt{dp}[x-1][y] + \texttt{dp}[x][y-1]$. Podemos usar esta recurrencia para calcular $\texttt{dp}[N][M]$. Hay que tener en cuenta que $\texttt{dp}[1][1] = 1$ porque el camino hasta $(1, 1)$ es una sola celda. En general, pensar cómo se pueden agregar celdas a los caminos ayuda a construir la recurrencia de DP correcta.

Al usar la recurrencia de DP, es importante calcular los valores en un orden tal que el valor de DP de una celda se conozca antes de usarlo para calcular el valor de DP de otra celda. En el problema de ejemplo de arriba, alcanza con iterar por cada fila de $0$ a $M-1$:

 
for (int i = 0; i < M; i++) {
	for (int j = 0; j < N; j++) {
		if (j > 0) dp[j][i] += dp[j - 1][i];
		if (i > 0) dp[j][i] += dp[j][i - 1];
	}
}

 
for (int i = 0; i < M; i++) {
	for (int j = 0; j < N; j++) {
		if (j > 0) dp[j][i] += dp[j - 1][i];
		if (i > 0) dp[j][i] += dp[j][i - 1];
	}
}

for i in range(M):
	for j in range(N):
		if j > 0:
			dp[j][i] += dp[j - 1][i]
		if i > 0:
			dp[j][i] += dp[j][i - 1]

Nótese que las coordenadas en el código están en la forma (coordenada $x$, coordenada $y$). La mayoría de las veces es más cómodo pensar los puntos como (fila, columna), lo que intercambia el orden de las coordenadas, aunque el código usa el formato anterior para ser consistente con la definición de $\texttt{dp}[x][y]$.

Solución - Grid Paths

En este problema nos dan directamente una grilla 2D de celdas, y hay que contar la cantidad de caminos de esquina a esquina que solo pueden ir hacia abajo (dirección $y$ positiva) y hacia la derecha (dirección $x$ positiva), con un detalle especial: el camino no puede usar una celda marcada con un asterisco.

Estamos cerca de poder usar la recurrencia original, pero hay que modificarla. Básicamente, si una celda $(x, y)$ es normal, usamos la recurrencia con normalidad. Pero si la celda $(x, y)$ tiene un asterisco, el valor de DP es $0$, porque ningún camino puede terminar en una trampa.

El código de la recurrencia de DP no cambia mucho:

#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
 
bool ok[1000][1000];
ll dp[1000][1000];
 
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
 
	int n;
	cin >> n;
	for (int i = 0; i < n; i++) {
		string s;
		cin >> s;
		for (int j = 0; j < n; j++) {
			if (s[j] == '.') ok[i][j] = true;
			else ok[i][j] = false;
		}
	}
 
	dp[0][0] = 1;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (!ok[i][j]) dp[i][j] = 0;
			else {
				if (i > 0) dp[i][j] += dp[i - 1][j];
				if (j > 0) dp[i][j] += dp[i][j - 1];
				dp[i][j] %= 1000000007;
			}
		}
	}
 
	cout << dp[n - 1][n - 1] << "\n";
 
	return 0;
}

 
import java.io.*;
import java.util.*;
 
public class Main {
 
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
		int N = Integer.parseInt(br.readLine());
		long dp[][] = new long[N][N];
		boolean ok[][] = new boolean[N][N];
		for (int i = 0; i < N; i++) {
			String s = br.readLine();
			for (int j = 0; j < N; j++) {
				if (s.charAt(j) == '.') ok[i][j] = true;
				else ok[i][j] = false;
			}
		}
 
		dp[0][0] = 1;
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				if (!ok[i][j]) dp[i][j] = 0;
				else {
					if (i > 0) dp[i][j] += dp[i - 1][j];
					if (j > 0) dp[i][j] += dp[i][j - 1];
					dp[i][j] %= 1000000007;
				}
			}
		}
 
		System.out.println(dp[N - 1][N - 1]);
	}
}

n = int(input())
ok = [[char == "." for char in input()] for _ in range(n)]
dp = [[0] * n for _ in range(n)]
dp[0][0] = 1
 
for i in range(n):
	for j in range(n):
		# si la casilla actual es una trampa
		if not ok[i][j]:
			dp[i][j] = 0
			continue
		if i - 1 >= 0:
			# sumar los caminos que terminan en la casilla de arriba
			dp[i][j] += dp[i - 1][j]
		if j - 1 >= 0:
			# sumar los caminos que terminan en la casilla de la izquierda
			dp[i][j] += dp[i][j - 1]
		dp[i][j] %= int(1e9 + 7)
 
print(dp[n - 1][n - 1])

Nótese que ahora las coordenadas están en la forma (fila, columna) al leer la entrada.

Solución - Longest Common Subsequence

La subsecuencia común más larga  es un problema clásico de strings, pero ¿dónde está la grilla?

De hecho, podemos crear una grilla para resolverlo. Pensemos el siguiente algoritmo para crear cualquier subsecuencia (no necesariamente la más larga) entre dos strings $A$ y $B$:

• Empezamos con dos punteros, $i$ y $j$, cada uno comenzando en $0$.
• En cada paso de tiempo hacemos alguna “acción”, hasta que no queden más “acciones” disponibles. Una “acción” puede ser cualquiera de las siguientes:

1. Aumentar el valor de $i$ en $1$ (solo funciona si $i < |A|$).
2. Aumentar el valor de $j$ en $1$ (solo funciona si $j < |B|$).
3. Aumentar el valor de $i$ y $j$ en $1$ solo si $A_i = B_j$. Agregar ese carácter $A_i$ (o $B_j$) a la subsecuencia común. (solo funciona si $i < |A|$ y $j < |B|$).

• Sabemos que este proceso crea una subsecuencia común porque los caracteres comunes a ambos strings se encuentran de izquierda a derecha.

Este algoritmo también se puede ilustrar en una grilla. Sean $A := xabcd$ y $B := yazc$. Entonces, el estado actual del algoritmo se puede definir como un punto específico $(i, j)$ usando los valores de $i$ y $j$ que discutimos antes. El proceso de aumentar punteros se puede ver como moverse a la derecha (si aumenta $i$), moverse hacia abajo (si aumenta $j$), o moverse en diagonal (si aumentan tanto $i$ como $j$). Observemos que cada movimiento diagonal suma uno a la longitud de la subsecuencia común.

Ahora reformulamos “la longitud de la subsecuencia creciente más larga” como “la cantidad máxima de ‘movimientos diagonales’ (la “acción 3” del algoritmo de arriba) en un camino desde la esquina superior izquierda hasta la esquina inferior derecha de la grilla”. Así construimos un problema de DP de tipo grilla.

En la grilla de arriba, el camino en negrita tiene movimientos diagonales en los caracteres “a” y “c”. Eso significa que la subsecuencia común más larga entre “xabcd” y “yazc” es “ac”.

A partir de las tres “acciones”, que también son los tres movimientos posibles del camino, podemos crear una recurrencia de DP para hallar la subsecuencia común más larga:

class Solution {
  public:
	int longestCommonSubsequence(string a, string b) {
		int dp[a.size()][b.size()];
		for (int i = 0; i < a.size(); i++) { fill(dp[i], dp[i] + b.size(), 0); }
		for (int i = 0; i < a.size(); i++) {
			if (a[i] == b[0]) dp[i][0] = 1;
			if (i != 0) dp[i][0] = max(dp[i][0], dp[i - 1][0]);
		}
		for (int i = 0; i < b.size(); i++) {
			if (a[0] == b[i]) dp[0][i] = 1;
			if (i != 0) dp[0][i] = max(dp[0][i], dp[0][i - 1]);
		}
		for (int i = 1; i < a.size(); i++) {
			for (int j = 1; j < b.size(); j++) {
				if (a[i] == b[j]) {
					dp[i][j] = dp[i - 1][j - 1] + 1;
				} else {
					dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
				}
			}
		}
		return dp[a.size() - 1][b.size() - 1];
	}
};

// CodeSnip{Benq Template}
class Solution {
  public:
	int longestCommonSubsequence(str a, str b) {
		V<vi> dp(sz(a) + 1, vi(sz(b) + 1));
		F0R(i, sz(a) + 1) F0R(j, sz(b) + 1) {
			if (i < sz(a)) ckmax(dp[i + 1][j], dp[i][j]);
			if (j < sz(b)) ckmax(dp[i][j + 1], dp[i][j]);
			if (i < sz(a) && j < sz(b))
				ckmax(dp[i + 1][j + 1], dp[i][j] + (a[i] == b[j]));
		}
		return dp[sz(a)][sz(b)];
	}
};

class Solution {
	public int longestCommonSubsequence(String a, String b) {
		int[][] dp = new int[a.length()][b.length()];
		for (int i = 0; i < a.length(); i++) {
			if (a.charAt(i) == b.charAt(0)) dp[i][0] = 1;
			if (i != 0) dp[i][0] = Math.max(dp[i][0], dp[i - 1][0]);
		}
		for (int i = 0; i < b.length(); i++) {
			if (a.charAt(0) == b.charAt(i)) { dp[0][i] = 1; }
			if (i != 0) dp[0][i] = Math.max(dp[0][i], dp[0][i - 1]);
		}
		for (int i = 1; i < a.length(); i++) {
			for (int j = 1; j < b.length(); j++) {
				if (a.charAt(i) == b.charAt(j)) {
					dp[i][j] = dp[i - 1][j - 1] + 1;
				} else {
					dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
				}
			}
		}
		return dp[a.length() - 1][b.length() - 1];
	}
}

class Solution:
	def longestCommonSubsequence(self, a: str, b: str) -> int:
		dp = [[0] * (len(b) + 1) for _ in range(len(a) + 1)]
		for i in range(1, len(a) + 1):
			for j in range(1, len(b) + 1):
				if a[i - 1] == b[j - 1]:
					dp[i][j] = dp[i - 1][j - 1] + 1
				else:
					dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
		return dp[len(a)][len(b)]

Problemas