Longest Increasing Path in a Matrix

DifícilProgramación dinámica Grafos Orden topológico

+10

Recibes matrix, una cuadrícula de números enteros con m filas y n columnas, como una lista de filas. Un camino va de una celda a otra, avanzando un paso hacia arriba, abajo, la izquierda o la derecha cada vez (sin pasos diagonales ni pasar de un borde al otro), y cada paso debe llegar a un valor estrictamente mayor. Devuelve el número de celdas del camino más largo de este tipo. Una celda por sí sola es un camino de 1 celda.

Función

longestIncreasingPath(matrix: integer-2d-array) → integer

matrixinteger-2d-array: la cuadrícula de valores, como una lista de filas de igual longitud
Devuelveinteger: el número de celdas en la ruta estrictamente creciente más larga

Restricciones

1 ≤ m, n ≤ 100, donde m = matrix.length y n = matrix[i].length
Cada fila tiene la misma longitud n.
0 ≤ matrix[i][j] ≤ 2³¹-1

Ejemplos

Entrada: matrix = [[9, 8, 3], [2, 7, 4], [1, 6, 5]]
Salida: 7
Explicación: El camino 3, 4, 5, 6, 7, 8, 9 baja por la columna de la derecha, va hacia la izquierda por la fila inferior, sube por la columna del medio y sigue hacia la izquierda hasta el 9 de la esquina: 7 celdas. El valor más pequeño da un resultado peor: desde el 1, los mejores caminos son 1, 2, 7, 8, 9 y 1, 6, 7, 8, 9, con 5 celdas cada uno.

+18 pruebas ocultas al enviar

Para ir más allá

¿También puedes devolver las celdas de uno de los caminos más largos, no solo su longitud?

Solución

Dibuja una flecha desde cada celda hacia cada vecina que tenga un valor mayor. Los valores aumentan a lo largo de cada flecha, así que ninguna cadena de flechas puede volver al punto de partida: la cuadrícula es un grafo acíclico dirigido, y la tarea consiste en encontrar su camino más largo. En un grafo general, esa pregunta es inviable para entradas grandes, pero, al no haber ciclos, el camino más largo desde una celda depende solo de esa celda, así que lo calculas una vez por celda y el problema completo se reduce a O(m × n). La búsqueda en profundidad con memorización lo calcula de arriba abajo; al eliminar capas de la cuadrícula desde sus picos, el algoritmo de Kahn en sentido inverso lo calcula de abajo arriba.

Sigue cada camino ascendente

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

Intuición

Inicia un recorrido en cada celda. Desde la celda en la que estás, prueba cada uno de los cuatro vecinos cuyo valor sea mayor y, desde allí, sigue avanzando de la misma manera hasta que no quede ningún vecino con un valor mayor. Cuenta las celdas de cada recorrido y conserva el mayor recuento.

El recorrido no necesita un conjunto de visitados. Los valores aumentan en cada paso, así que el recorrido nunca puede volver a una celda: para volver a estar en ella, tendría que descender hasta el valor de esa celda. Mantén los recorridos en una pila de entradas (celda, longitud). Sacar una entrada de la pila termina un recorrido en esa celda, y añadir sus vecinos con valores mayores lo prolonga.

El método es correcto y desesperadamente lento, porque los recorridos se ramifican. En una cuadrícula de 100 × 100 donde cada valor es la suma de su fila y su columna, cada paso a la derecha o hacia abajo es un paso ascendente, y solo los recorridos que parten de la esquina superior izquierda suman más de 10^58. Peor aún, el recorrido desde cualquier celda se repite cada vez que otro recorrido pasa por ella, y ese es el desperdicio que elimina el siguiente enfoque.

Algoritmo

Para cada celda, apila (esa celda, 1) en una pila.
Desapila una entrada (celda, longitud) y actualiza la respuesta con la longitud.
Apila (vecina, longitud + 1) por cada vecina dentro de la cuadrícula con un valor estrictamente mayor.
Repite hasta que la pila esté vacía; después, pasa a la siguiente celda inicial.
Devuelve la longitud mayor encontrada.

def longestIncreasingPath(matrix):
    rows, cols = len(matrix), len(matrix[0])
    dirs = ((1, 0), (-1, 0), (0, 1), (0, -1))
    answer = 0
    for sr in range(rows):
        for sc in range(cols):
            # Each entry is one path in progress: the cell it ends on and
            # how many cells it has.
            stack = [(sr, sc, 1)]
            while stack:
                r, c, length = stack.pop()
                answer = max(answer, length)
                for dr, dc in dirs:
                    nr, nc = r + dr, c + dc
                    if 0 <= nr < rows and 0 <= nc < cols and matrix[nr][nc] > matrix[r][c]:
                        stack.append((nr, nc, length + 1))
    return answer

Búsqueda en profundidad con memorización y tu propia pila

Intuición

Sea best[cell] el número de celdas en el camino creciente más largo que comienza en esa celda. El camino termina allí mismo, o su siguiente paso va a un vecino mayor y continúa por el camino más largo desde ese vecino. Así que best[cell] = 1 + max(best[nb]) entre los vecinos mayores nb, o 1 si no hay ninguno. Es seguro reutilizar este resultado debido a la estructura acíclica: las celdas anteriores a cell en cualquier camino son todas menores, así que nunca pueden aparecer después de ella, y la mejor continuación desde cell es la misma sin importar cómo hayas llegado. Calcula cada best una sola vez y guárdalo; el árbol exponencial de recorridos se reduce a una visita por celda.

En el primer ejemplo, 9 no tiene vecinos mayores, así que best vale 1 allí. Después, 8 obtiene 2, 7 obtiene 3, 6 y 2 obtienen 4, 5 y 1 obtienen 5, 4 obtiene 6 y 3 obtiene 7, que es la respuesta. Cada celda revisa sus 4 vecinos, así que el trabajo es O(m × n).

El código natural es recursivo: una función que devuelve best para una celda y se llama a sí misma para cada vecino mayor. La profundidad de las llamadas equivale a la longitud del camino que sigue, y las restricciones permiten un camino que atraviesa todas las celdas: valores que serpentean de un lado a otro por una cuadrícula de 100 × 100 forman un camino de 10,000 celdas, mientras que Python se detiene de forma predeterminada tras 1,000 llamadas anidadas. El código siguiente ejecuta la recursión por sí mismo, así que ningún camino es demasiado largo para él. Mantén una pila de celdas y, para cada celda, cuántas de sus cuatro direcciones has probado. Mira la celda del extremo superior: si le queda una dirección, pruébala y añade a la pila el vecino de esa dirección cuando sea mayor y aún no esté terminado. Cuando hayas probado las cuatro, todos los vecinos mayores estarán terminados, así que saca la celda de la pila y establece su best. Este es exactamente el orden que seguiría una llamada recursiva.

La búsqueda no necesita ninguna marca de «en curso», a diferencia de la detección de ciclos. Cada celda de la pila es mayor que la que está debajo, así que un vecino mayor de la celda del extremo superior nunca puede estar más abajo en la pila.

Algoritmo

Rellena best con 0 (aún no se conoce) y un contador de direcciones con 0 para cada celda.
Para cada celda cuyo best sea 0, colócala en una pila.
Mira la celda de la parte superior. Si le queda una dirección por probar, incrementa su contador y coloca en la pila la celda vecina en esa dirección si está dentro de la cuadrícula, tiene un valor mayor y no ha terminado.
Si se han probado las cuatro direcciones, saca la celda de la pila y establece best en 1 más el mayor best entre sus vecinas con valores mayores, o en 1 si no tiene ninguna.
Devuelve el mayor best.

def longestIncreasingPath(matrix):
    rows, cols = len(matrix), len(matrix[0])
    dirs = ((1, 0), (-1, 0), (0, 1), (0, -1))
    # best[r][c]: cells on the longest increasing path that starts at (r, c).
    # 0 means not known yet.
    best = [[0] * cols for _ in range(rows)]
    # step[r][c]: how many of the 4 directions the search has tried from (r, c).
    step = [[0] * cols for _ in range(rows)]
    answer = 0
    for sr in range(rows):
        for sc in range(cols):
            if best[sr][sc]:
                continue
            # Our own stack instead of recursion: a path can be thousands of
            # cells long, past Python's limit of 1,000 nested calls.
            stack = [(sr, sc)]
            while stack:
                r, c = stack[-1]
                d = step[r][c]
                if d < 4:
                    step[r][c] = d + 1
                    nr, nc = r + dirs[d][0], c + dirs[d][1]
                    # The stack only climbs, so a larger neighbour is never on it.
                    if 0 <= nr < rows and 0 <= nc < cols and matrix[nr][nc] > matrix[r][c] and best[nr][nc] == 0:
                        stack.append((nr, nc))
                    continue
                # Every larger neighbour is finished: build on the best of them.
                stack.pop()
                length = 1
                for dr, dc in dirs:
                    nr, nc = r + dr, c + dc
                    if 0 <= nr < rows and 0 <= nc < cols and matrix[nr][nc] > matrix[r][c]:
                        length = max(length, best[nr][nc] + 1)
                best[r][c] = length
                answer = max(answer, length)
    return answer

Despega la cuadrícula desde sus picos

Intuición

Invierte la programación dinámica y constrúyela desde los valores más altos hacia abajo, como hace el algoritmo de Kahn para construir un orden topológico. Llama cima a una celda cuando ningún vecino sea mayor. Un camino desde una cima no puede avanzar, así que tiene 1 celda. Elimina todas las cimas a la vez: esa es la capa 1. Ahora algunas celdas han perdido a su último vecino mayor, así que son las cimas de lo que queda. Elimínalas como capa 2 y sigue así hasta que la cuadrícula esté vacía. El número de capas es la respuesta.

Por qué: una celda queda en la capa k exactamente cuando el camino más largo que empieza en ella tiene k celdas. Una celda se elimina en la ronda posterior a la eliminación de su último vecino mayor, así que su capa es 1 más que la capa más alta entre sus vecinos mayores, que es la fórmula best[cell] = 1 + max(best[nb]) del enfoque anterior. La capa más profunda corresponde al inicio de un camino más largo.

En el primer ejemplo, la única cima es el 9 (sus vecinos son 8 y 2). Al eliminarlo, se libera el 8; al eliminar el 8, se libera el 7; al eliminar el 7, se liberan el 2 y el 6; esos dos liberan el 1 y el 5; el 5 libera el 4, y el 4 libera el 3. Son 7 capas, y el camino 3, 4, 5, 6, 7, 8, 9 asciende pasando por una celda de cada una.

Para encontrar rápidamente la siguiente capa, cuenta cuántos vecinos mayores le quedan a cada celda. Al eliminar una celda, disminuye el contador de cada vecino estrictamente menor, y cuando un contador llega a 0, ese vecino pasa a la siguiente capa. Cada celda se elimina una vez y cada par de vecinos se examina un número constante de veces, así que el trabajo es O(m × n), sin pila ni recursión.

Algoritmo

Para cada celda, cuenta los vecinos con un valor mayor.
Coloca en la capa actual cada celda cuyo recuento sea 0.
Mientras la capa no esté vacía, suma 1 al recuento de capas. Para cada celda de la capa, reduce el recuento de cada vecino estrictamente menor y coloca en la capa siguiente cualquier vecino cuyo recuento llegue a 0.
Haz que la capa siguiente sea la actual y repite.
Devuelve el recuento de capas.

def longestIncreasingPath(matrix):
    rows, cols = len(matrix), len(matrix[0])
    dirs = ((1, 0), (-1, 0), (0, 1), (0, -1))
    # higher[r][c]: neighbours of (r, c) with a larger value, not peeled yet.
    higher = [[0] * cols for _ in range(rows)]
    layer = []
    for r in range(rows):
        for c in range(cols):
            for dr, dc in dirs:
                nr, nc = r + dr, c + dc
                if 0 <= nr < rows and 0 <= nc < cols and matrix[nr][nc] > matrix[r][c]:
                    higher[r][c] += 1
            # A peak: no neighbour is larger, so a path from it has one cell.
            if higher[r][c] == 0:
                layer.append((r, c))
    layers = 0
    while layer:
        layers += 1
        next_layer = []
        for r, c in layer:
            for dr, dc in dirs:
                nr, nc = r + dr, c + dc
                if 0 <= nr < rows and 0 <= nc < cols and matrix[nr][nc] < matrix[r][c]:
                    higher[nr][nc] -= 1
                    # Its last larger neighbour is peeled: it is a peak now.
                    if higher[nr][nc] == 0:
                        next_layer.append((nr, nc))
        layer = next_layer
    # Each layer is one step further from a peak; the count is the longest path.
    return layers

Errores comunes y casos límite

Los errores de aquí se deben a la palabra «estrictamente», a la recursión profunda y a los hábitos heredados de otros problemas con cuadrículas.

Comparar con >= en lugar de con >. Con dos 4 vecinos, cada uno cuenta como un paso hacia arriba desde el otro; las flechas forman un ciclo, un método de fuerza bruta va y viene para siempre, y una búsqueda con memorización lee una longitud que todavía se está calculando.
Recurrir en caminos muy largos. Una búsqueda recursiva alcanza tantos niveles de llamadas como largo sea el camino, y las restricciones permiten un camino que atraviesa todas las celdas: valores que serpentean de un lado a otro por una cuadrícula de 100 × 100 forman un camino de 10.000 celdas, diez veces el límite predeterminado de Python de 1.000 llamadas anidadas. Los caminos tan largos necesitan una búsqueda iterativa con una pila propia, o un límite de recursión aumentado (sys.setrecursionlimit en Python); aun así, un límite muy alto puede desbordar la propia pila del intérprete.
Omitir las celdas ya visitadas, como en un relleno por inundación. Llegar a una celda ya procesada no es un callejón sin salida: su longitud almacenada es exactamente lo que necesita la celda actual. Léela, no la omitas.
Empezar solo por el valor más pequeño. En el primer ejemplo, el 1 da 5 celdas, pero la respuesta, 7, empieza en el 3. El camino más largo puede empezar en cualquier celda que no tenga un vecino más pequeño, y puede haber muchas.
Devolver 0. Cada celda es un camino de 1 celda, así que una cuadrícula de valores iguales, o una cuadrícula de 1 × 1, tiene respuesta 1. Empieza la longitud de cada celda en 1, no en 0.
En el método de eliminación por capas, reducir el contador de un vecino igual. Solo un vecino estrictamente más pequeño ha perdido uno mayor.

Preguntas frecuentes4

¿Cuál es la complejidad temporal de la ruta creciente más larga en una matriz?

Tiempo O(m × n) y espacio O(m × n) con búsqueda en profundidad con memoización o con eliminación topológica. Cada una de las m × n celdas se procesa una vez y examina sus 4 vecinas un número constante de veces, y cada método guarda un número por celda. Probar todos los caminos desde cada celda es exponencial: en una cuadrícula de 100 × 100 donde cada valor es la suma de su fila y su columna, más de 10^58 caminos salen de la esquina superior izquierda.

¿Por qué este problema no necesita un conjunto de visitados?

Un camino que solo asciende nunca puede volver a una celda, porque tendría que volver a bajar al valor de esa celda. Así que la regla estrictamente creciente ya prohíbe las revisitas, y el grafo de pasos no tiene ciclos. Por eso también es seguro usar la memorización: las celdas anteriores a una celda determinada no pueden interferir con el camino que viene después.

¿Longest Increasing Path in a Matrix es un problema de programación dinámica o de grafos?

Ambos. Es el camino más largo en un grafo acíclico dirigido, lo que corresponde a programación dinámica sobre un orden topológico: la respuesta de una celda es 1 más la mejor respuesta entre sus vecinos de mayor valor. La búsqueda en profundidad con memoización llena la tabla en el orden en que la búsqueda termina de procesar las celdas, y la eliminación topológica la llena capa por capa, empezando por los picos. Ordenar las celdas de mayor a menor valor da un tercer orden válido, con un coste de O(m × n × log(m × n)) para la ordenación.

¿En qué se diferencia esto de la subsecuencia creciente más larga?

Una subsecuencia puede saltarse elementos y debe mantener su orden, mientras que aquí un camino debe avanzar a una celda adyacente, en cualquiera de las cuatro direcciones. El problema de la subsecuencia se resuelve mediante programación dinámica en una línea; este se resuelve mediante programación dinámica en una cuadrícula convertida en un grafo. Ambos se basan en el mismo hecho: una cadena estrictamente creciente nunca puede volver sobre sí misma.

Python

def longestIncreasingPath(matrix):
    # Escribe el código aquí

Casos de prueba

Caso 1

Caso 2

Caso 3

Entrada

matrix = [[9, 8, 3], [2, 7, 4], [1, 6, 5]]

Esperado

Longest Increasing Path in a Matrix

Función

Restricciones

Ejemplos

Pistas

Solución

Sigue cada camino ascendente

Búsqueda en profundidad con memorización y tu propia pila

Despega la cuadrícula desde sus picos

Errores comunes y casos límite

Preguntas frecuentes4

Problemas similares