DP 2D en Matrices

Blog 3: Dominando la Programación Dinámica en Rejillas 2D Matrix Problems

La Programación Dinámica en rejillas 2D es un patrón fundamental para resolver problemas reales como búsqueda de rutas, navegación de robots, tableros de juego, recorridos con obstáculos y recolección de recursos. La idea clave es avanzar celda a celda en una matriz, tomando decisiones locales que acumulan el mejor resultado global. En Q2BSTUDIO, empresa de desarrollo de software a medida y aplicaciones a medida, aplicamos estas técnicas en soluciones de inteligencia artificial, ciberseguridad, automatización de procesos y analítica avanzada para maximizar el valor de negocio.

Cómo pensar un DP de rejilla

1. Estado: dp[i][j] representa el mejor valor o el número de formas para alcanzar la celda i, j. 2. Transición: llegar a dp[i][j] desde arriba i-1, j o izquierda i, j-1, y en algunas variantes también en diagonal. 3. Casos base: la celda de inicio 0,0 y las primeras filas o columnas. 4. Respuesta: a menudo en dp[m-1][n-1].

Ejemplo 1: Caminos únicos contar todas las formas

Problema: Un robot solo puede moverse a la derecha o hacia abajo en una cuadrícula m x n. Cuántos caminos únicos existen hasta la esquina inferior derecha

Idea: Si estás en i, j solo pudiste venir desde arriba i-1, j o izquierda i, j-1. Suma ambas cantidades.

Código Java:

public class UniquePaths { public int uniquePaths int m, int n { int[][] dp = new int[m][n]; // Inicializar primera fila y primera columna hay 1 forma de avanzar recto for int i = 0; i < m; i++ dp[i][0] = 1; for int j = 0; j < n; j++ dp[0][j] = 1; // Rellenar el resto de la rejilla for int i = 1; i < m; i++ { for int j = 1; j < n; j++ { dp[i][j] = dp[i-1][j] + dp[i][j-1]; } } return dp[m-1][n-1]; } }

Ejemplo 2: Caminos únicos con obstáculos

Problema: Igual que el anterior, pero con celdas bloqueadas 1 es obstáculo.

Idea: Si hay obstáculo, dp[i][j] = 0. Si no, dp[i][j] = desde arriba + desde izquierda.

Código Java:

public class UniquePathsWithObstacles { public int uniquePathsWithObstacles int[][] grid { int m = grid.length, n = grid[0].length; int[][] dp = new int[m][n]; // Si el inicio está bloqueado no hay camino if grid[0][0] == 1 return 0; dp[0][0] = 1; for int i = 0; i < m; i++ { for int j = 0; j < n; j++ { if grid[i][j] == 1 { 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]; } } } return dp[m-1][n-1]; } }

Ejemplo 3: Suma mínima de camino

Problema: Cada celda tiene un coste. Encuentra el coste mínimo para llegar a la esquina inferior derecha.

Idea: En i, j toma el mínimo entre venir desde arriba o desde izquierda y suma el coste actual.

Código Java:

public class MinPathSum { public int minPathSum int[][] grid { int m = grid.length, n = grid[0].length; int[][] dp = new int[m][n]; dp[0][0] = grid[0][0]; // Primera fila for int j = 1; j < n; j++ dp[0][j] = dp[0][j-1] + grid[0][j]; // Primera columna for int i = 1; i < m; i++ dp[i][0] = dp[i-1][0] + grid[i][0]; for int i = 1; i < m; i++ { for int j = 1; j < n; j++ { dp[i][j] = Math.min dp[i-1][j], dp[i][j-1] + grid[i][j]; } } return dp[m-1][n-1]; } }

Ejemplo 4: Suma máxima de camino recolectar el máximo de monedas

Problema: Cada celda tiene monedas. Recolecta el máximo moviéndote de arriba a la izquierda a abajo a la derecha.

Idea: Igual que el mínimo, pero tomando el máximo.

Código Java:

public class MaxPathSum { public int maxPathSum int[][] grid { int m = grid.length, n = grid[0].length; int[][] dp = new int[m][n]; dp[0][0] = grid[0][0]; for int j = 1; j < n; j++ dp[0][j] = dp[0][j-1] + grid[0][j]; for int i = 1; i < m; i++ dp[i][0] = dp[i-1][0] + grid[i][0]; for int i = 1; i < m; i++ { for int j = 1; j < n; j++ { dp[i][j] = Math.max dp[i-1][j], dp[i][j-1] + grid[i][j]; } } return dp[m-1][n-1]; } }

Ejemplo 5: Ruta descendente mínima con diagonales

Problema: Desde la primera fila baja hasta la última. En cada paso puedes ir hacia abajo, abajo izquierda o abajo derecha. Minimiza la suma.

Idea: Cada celda depende de tres padres posibles.

Código Java:

public class MinFallingPathSum { public int minFallingPathSum int[][] matrix { int n = matrix.length; int[][] dp = new int[n][n]; // Copiar primera fila for int j = 0; j < n; j++ dp[0][j] = matrix[0][j]; for int i = 1; i < n; i++ { for int j = 0; j < n; j++ { int minPrev = dp[i-1][j]; if j > 0 minPrev = Math.min minPrev, dp[i-1][j-1]; if j < n-1 minPrev = Math.min minPrev, dp[i-1][j+1]; dp[i][j] = matrix[i][j] + minPrev; } } int ans = Integer.MAX_VALUE; for int j = 0; j < n; j++ ans = Math.min ans, dp[n-1][j]; return ans; } }

Ejemplo 6: Cherry Pickup dos robots maximizando la recolección

Problema: Dos robots parten en 0,0 y 0, n-1 y bajan hasta la última fila. Cada celda tiene cerezas. Si ambos pisan la misma celda se cuenta una sola vez. Maximiza la recolección.

Idea: Estado fila, col1, col2. Transiciones en 9 combinaciones de movimientos para ambas columnas -1, 0, 1.

Código Java recursivo con memoización:

public class CherryPickup { int[][][] memo; public int cherryPickup int[][] grid { int m = grid.length, n = grid[0].length; memo = new int[m][n][n]; for int[][] layer : memo for int[] row : layer Arrays.fill row, -1; return dfs grid, 0, 0, n-1; } private int dfs int[][] grid, int row, int col1, int col2 { int m = grid.length, n = grid[0].length; if col1 < 0 || col1 >= n || col2 < 0 || col2 >= n return 0; if row == m return 0; if memo[row][col1][col2] != -1 return memo[row][col1][col2]; int cherries = grid[row][col1]; if col1 != col2 cherries += grid[row][col2]; int max = 0; for int d1 = -1; d1 <= 1; d1++ { for int d2 = -1; d2 <= 1; d2++ { max = Math.max max, dfs grid, row+1, col1+d1, col2+d2; } } return memo[row][col1][col2] = cherries + max; } }

Claves prácticas y optimización

1. Piensa siempre en cómo llegas a cada celda y qué agregas al estado. 2. Define casos base sólidos celdas de inicio, primeras filas o columnas, y celdas bloqueadas. 3. Optimiza espacio con arreglos 1D si solo necesitas la fila o columna anterior. 4. Este patrón se usa más allá de juegos en logística, robótica, rutas más cortas o baratas, planificación de recursos y sistemas de recomendación.

Cómo lo aplicamos en Q2BSTUDIO

En Q2BSTUDIO construimos soluciones de software a medida y aplicaciones a medida que integran algoritmos de Programación Dinámica y modelos de inteligencia artificial para optimizar rutas, asignar recursos, detectar anomalías y acelerar la toma de decisiones. Si quieres incorporar ia para empresas y agentes IA en tus productos o procesos, visítanos en nuestra página de inteligencia artificial. También desarrollamos plataformas multiplataforma robustas y escalables con las mejores prácticas de arquitectura, consulta nuestro enfoque de software a medida y aplicaciones a medida.

Además ofrecemos ciberseguridad y pentesting para proteger tus activos, servicios cloud aws y azure para desplegar soluciones elásticas y seguras, y servicios inteligencia de negocio con power bi para convertir datos en decisiones. Si buscas ventaja competitiva con algoritmos eficientes, automatización y datos accionables, nuestro equipo puede ayudarte a llevar tu producto del concepto a la producción con calidad empresarial.