Unique Paths

Q: ¿Cuál es la fórmula de caminos únicos?

La respuesta es el coeficiente binomial C(m+n-2, m-1) . Cada camino realiza m-1 movimientos hacia abajo y n-1 movimientos hacia la derecha en algún orden, y elegir cuáles de los m+n-2 movimientos van hacia abajo determina el camino. Para una cuadrícula de 3 × 4, es C(5, 2) = 10.

MedioProgramación dinámica Matemáticas y simulación

+10

Un robot comienza en la celda superior izquierda de una cuadrícula con m filas y n columnas y debe llegar a la celda inferior derecha. Cada movimiento lo desplaza una celda a la derecha o una celda hacia abajo. Devuelve el número de caminos diferentes que puede tomar.

Función

uniquePaths(m: integer, n: integer) → integer

minteger: el número de filas de la cuadrícula
ninteger: el número de columnas de la cuadrícula
Devuelveinteger: el número de caminos diferentes desde la celda superior izquierda hasta la celda inferior derecha

Restricciones

1 ≤ m, n ≤ 100
La respuesta es como máximo 2 × 10⁹, así que cabe en un entero con signo de 32 bits.

Ejemplos

Entrada: m = 3n = 4
Salida: 10
Explicación: Cada camino hace 2 movimientos hacia abajo y 3 movimientos hacia la derecha, 5 movimientos en total. Un camino queda determinado por cuáles 2 de los 5 movimientos van hacia abajo, y hay 10 maneras de elegirlos.

+14 pruebas ocultas al enviar

Para ir más allá

Para una cuadrícula de 100 × 100, la respuesta tiene 59 dígitos. ¿Cómo la devolverías módulo 10^9+7 usando la fórmula, cuando dividir por i ya no funciona?

Pistas

Ábrelas de una en una. Cada una revela un poco más.

0 de 3 abiertas

Solución

Enumerar los caminos uno por uno es inútil: una cuadrícula de 17 × 17 ya tiene 601,080,390. Hay que contarlos sin enumerarlos. Los caminos que llegan a una celda son los que llegan a la celda de arriba más los que llegan a la celda de la izquierda, lo que convierte la cuadrícula en una tabla que se completa en una sola pasada. Un camino también es simplemente un orden de movimientos hacia abajo y hacia la derecha, y eso proporciona una fórmula cerrada.

Cuenta cada ruta con recursión

Correcto, pero no termina con las pruebas más grandes

Intuición

Piensa en el último movimiento del robot hasta la celda inferior derecha. Llegó desde abajo de la celda de arriba o desde la derecha de la celda de la izquierda, nunca de ambas formas. Así que las rutas por una cuadrícula de m × n son las rutas por la cuadrícula con una fila menos, uniquePaths(m-1, n), más las rutas por la cuadrícula con una columna menos, uniquePaths(m, n-1).

La recursión se detiene en una cuadrícula con una fila o una columna, donde el robot solo puede avanzar en línea recta, así que hay exactamente 1 ruta. Todas las rutas terminan con uno de los dos movimientos, por lo que cada ruta se cuenta una vez y el total es correcto.

Es lento porque todas las rutas terminan en un caso base que devuelve 1, así que el número de llamadas es al menos igual a la respuesta. Una cuadrícula de 17 × 17 requiere más de 600 millones de llamadas, y las pruebas llegan a respuestas cercanas a 1.6 × 10^9. Las mismas cuadrículas más pequeñas se calculan muchas veces: se llega a (m-1, n-1) una vez desde cada uno de sus dos nodos principales, y las repeticiones se multiplican a medida que avanzas hacia abajo.

Algoritmo

Si m o n es 1, devuelve 1: el único camino es una línea recta.
De lo contrario, cuenta los caminos cuyo último movimiento es hacia abajo, uniquePaths(m-1, n).
Cuenta los caminos cuyo último movimiento es hacia la derecha, uniquePaths(m, n-1).
Devuelve su suma.

def uniquePaths(m, n):
    # One row or one column: the only path is a straight line
    if m == 1 or n == 1:
        return 1
    # The last move came down from the row above or right from the column before
    return uniquePaths(m - 1, n) + uniquePaths(m, n - 1)

Rellena la cuadrícula una fila a la vez

Intuición

La recursión pregunta por las mismas celdas una y otra vez, y solo hay m × n celdas. Cuenta una sola vez los caminos que llegan a cada celda, en un orden en el que las celdas que necesitas ya estén listas.

Estado: paths[r][c] es el número de caminos desde la celda superior izquierda hasta la fila r, columna c. Recurrencia: paths[r][c] = paths[r-1][c] + paths[r][c-1], los caminos que llegan desde arriba más los caminos que llegan desde la izquierda. Casos base: cada celda de la fila superior y de la columna izquierda tiene 1 camino, en línea recta. Orden: fila por fila, de izquierda a derecha, para que la celda de arriba y la celda de la izquierda estén rellenadas antes de necesitarlas.

Para m = 3 y n = 4, las filas son 1 1 1 1, después 1 2 3 4, después 1 3 6 10, y la respuesta es la última celda, 10.

Ahora fíjate en qué lee el rellenado: solo la fila de arriba y la fila que estás rellenando. Así que conserva una fila. Antes de actualizar row[c], todavía contiene el recuento de la fila de arriba, y row[c-1] ya contiene el nuevo recuento a su izquierda, así que row[c] += row[c-1] es toda la recurrencia. El tiempo sigue siendo O(m × n), y la memoria se reduce de O(m × n) a O(n).

Algoritmo

Haz row con n entradas, todas 1: la fila superior.
Repite m-1 veces, una por cada fila debajo de la superior.
En cada fila, para c desde 1 hasta n-1, suma row[c-1] a row[c]. row[0] se mantiene en 1: esa es la columna izquierda.
Devuelve row[n-1].

def uniquePaths(m, n):
    # row[c] counts the paths into column c of the current row.
    # The top row is all 1s: the only way along it is straight right.
    row = [1] * n
    for _ in range(m - 1):
        for c in range(1, n):
            # Paths from above (the old row[c]) plus paths from the left (the new row[c-1])
            row[c] += row[c - 1]
    return row[n - 1]

Cuenta los movimientos con un coeficiente binomial

Intuición

Cada camino realiza exactamente m-1 movimientos hacia abajo y n-1 movimientos hacia la derecha, m+n-2 movimientos en total, en algún orden. Cualquier orden es un camino válido: el robot nunca realiza más de m-1 movimientos hacia abajo ni más de n-1 movimientos hacia la derecha, así que nunca sale de la cuadrícula. Por lo tanto, un camino equivale a elegir cuáles m-1 de los m+n-2 movimientos se hacen hacia abajo, y la respuesta es el coeficiente binomial C(m+n-2, m-1).

La tabla del enfoque anterior es el triángulo de Pascal girado de lado, por eso ambos coinciden. Para calcular el coeficiente sin factoriales enormes, constrúyelo multiplicando por un factor a la vez. Con N = m+n-2 y k = min(m, n)-1, multiplica por N-k+i y después divide por i, para i desde 1 hasta k. Después del paso i, el valor acumulado es C(N-k+i, i), un número entero, así que cada división es exacta.

Para m = 3 y n = 4: N = 5, k = 2, y el valor pasa de 1 × 4 / 1 = 4 a 4 × 5 / 2 = 10. Elegir a lo largo del lado más corto mantiene el bucle en 99 pasos o menos. El producto antes de la última división es k veces la respuesta. Para una cuadrícula de 17 × 17, eso es 16 × 601,080,390, aproximadamente 9.6 × 10^9, por encima del rango de 32 bits, así que guárdalo en un entero de 64 bits.

Algoritmo

Establece N = m+n-2, el número de movimientos, y k = min(m, n)-1.
Inicia un contador de 64 bits en 1.
Para i desde 1 hasta k, multiplica el contador por N-k+i y después divídelo por i.
Devuelve el contador.

def uniquePaths(m, n):
    # A path is m+n-2 moves; count the ways to choose which of them go down.
    # Choose along the shorter side so the loop stays short.
    moves = m + n - 2
    k = min(m, n) - 1
    count = 1
    for i in range(1, k + 1):
        # count goes from C(moves-k+i-1, i-1) to C(moves-k+i, i); the division is exact
        count = count * (moves - k + i) // i
    return count

Errores comunes y casos límite

El recuento es breve, así que los errores se esconden en los bordes de la cuadrícula y en el tamaño de los números.

Calcular (m+n-2)! y dividir entre los otros dos factoriales provoca un desbordamiento mucho antes de obtener la respuesta: 21! ya supera el rango de 64 bits, y m+n-2 llega a 105 en una cuadrícula de 100 × 7.
Dividir antes de multiplicar, como en count / i * (N-k+i), trunca el resultado, porque count no siempre es múltiplo de i. Multiplica primero: el producto siempre se divide exactamente.
El producto count × (N-k+i) puede superar 2^31 aunque la respuesta no lo supere. Guárdalo en un entero de 64 bits.
Dejar la fila superior o la columna izquierda en 0 en lugar de 1 hace que todas las celdas sean 0. Una cuadrícula con una fila o una columna tiene exactamente 1 camino.
Intercambiar las filas y las columnas no cambia la respuesta, ya que C(m+n-2, m-1) = C(m+n-2, n-1).

Preguntas frecuentes4

¿Cuál es la fórmula de caminos únicos?

La respuesta es el coeficiente binomial C(m+n-2, m-1). Cada camino realiza m-1 movimientos hacia abajo y n-1 movimientos hacia la derecha en algún orden, y elegir cuáles de los m+n-2 movimientos van hacia abajo determina el camino. Para una cuadrícula de 3 × 4, es C(5, 2) = 10.

¿Cuál es la complejidad temporal de Unique Paths?

La tabla de programación dinámica requiere un tiempo de O(m × n) y un espacio de O(n) si mantienes una fila. La fórmula binomial requiere un tiempo de O(min(m, n)) y un espacio de O(1). La recursión simple realiza al menos tantas llamadas como caminos hay, lo que es exponencial en m + n.

¿Cómo se resuelven los caminos únicos cuando algunas celdas están bloqueadas?

Usa la misma tabla y establece en 0 el conteo de una celda bloqueada para que ningún camino pase por ella. La fila superior y la columna izquierda dejan de estar llenas de 1: cada celda después de una bloqueada en la fila superior tiene 0 caminos. La fórmula ya no funciona porque supone que se permite cualquier orden de movimientos.

¿Por qué la tabla de caminos únicos coincide con el triángulo de Pascal?

Cada celda suma la celda de arriba y la celda de su izquierda, que es la regla que construye el triángulo de Pascal, leído a lo largo de sus diagonales. La celda de la fila r y la columna c contiene C(r+c, r), así que la celda de la esquina inferior derecha contiene C(m+n-2, m-1).

Python

def uniquePaths(m, n):
    # Escribe el código aquí

Casos de prueba

Caso 1

Caso 2

Caso 3

Entrada

m = 3
n = 4

Esperado

Unique Paths

Función

Restricciones

Ejemplos

Pistas

Solución

Cuenta cada ruta con recursión

Rellena la cuadrícula una fila a la vez

Cuenta los movimientos con un coeficiente binomial

Errores comunes y casos límite

Preguntas frecuentes4

Problemas similares