Conteo de caminos en una cuadrícula

Empiece en la esquina superior izquierda de una cuadrícula y llegue hasta la esquina inferior derecha. Cada paso se mueve a la derecha o hacia abajo. ¿Cuántos caminos distintos existen?

Cada celda se puede alcanzar desde la celda de arriba o desde la de la izquierda. Esa superposición explica exactamente por qué este es un problema de DP.

Sea dp[i][j] el número de formas de llegar a la celda (i, j) desde el inicio. Nombrar claramente el estado es la mitad del trabajo.

Solo puede llegar desde arriba o desde la izquierda, así que el conteo es su suma. Esta es la transición que impulsa toda la tabla.

Solo hay una forma de llegar a la celda inicial: no hacer nada. Por tanto, dp[0][0] es 1 antes de rellenar cualquier otra celda.

Las celdas de la fila superior o de la columna izquierda tienen una única ruta en línea recta. Su conteo siempre es 1, ya que uno de sus vecinos queda fuera de la cuadrícula.

Cree una tabla de m por n llena de ceros. Determinar su tamaño de antemano mantiene los índices limpios y evita sorpresas.

Recorra primero las filas y después las columnas, de arriba abajo y de izquierda a derecha. Este orden garantiza que ambos vecinos estén listos antes de utilizarlos.

Después de rellenar la tabla, el conteo de caminos se encuentra en la última celda. La respuesta es dp[m-1][n-1], la esquina inferior derecha.

Cada fila solo necesita la fila anterior, así que puede conservar una sola fila y actualizarla en el mismo lugar. Esto reduce la memoria a O(n).

Sin bloques, la respuesta es un coeficiente binomial: elija cuáles de los pasos totales se hacen hacia abajo. La DP sigue siendo la mejor opción cuando aparecen obstáculos.

Está rellenando dp[i][j] para una celda interior libre. ¿Qué fórmula es correcta?

Defina dp como los caminos hasta una celda, establezca dp[0][0] en 1 y sume la celda de arriba y la de la izquierda. La esquina contiene su respuesta. 🧭