Longest Increasing Path in a Matrix

СложноДинамическое программирование Графы Топологическая сортировка

+10

Тебе дана matrix — сетка целых чисел с m строками и n столбцами, представленная в виде списка строк. Путь проходит от одной ячейки к другой, каждый раз на один шаг вверх, вниз, влево или вправо (диагональные шаги и выход за границы не допускаются), и каждый шаг должен вести к строго большему значению. Верни количество ячеек в самом длинном таком пути. Одна ячейка сама по себе образует путь из 1 ячейки.

Функция

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

matrixinteger-2d-array: сетка значений в виде списка строк одинаковой длины
Возвращаетinteger: количество ячеек в самом длинном строго возрастающем пути

Ограничения

1 ≤ m, n ≤ 100, где m = matrix.length и n = matrix[i].length
Каждая строка имеет одинаковую длину n.
0 ≤ matrix[i][j] ≤ 2³¹-1

Примеры

Ввод: matrix = [[9, 8, 3], [2, 7, 4], [1, 6, 5]]
Вывод: 7
Пояснение: Путь 3, 4, 5, 6, 7, 8, 9 проходит вниз по правому столбцу, влево по нижней строке, вверх по среднему столбцу и влево к 9 в углу: 7 клеток. С наименьшим значением результат хуже: от 1 лучшие пути — 1, 2, 7, 8, 9 и 1, 6, 7, 8, 9, по 5 клеток каждый.

+18 скрытых тестов при отправке

Дополнительный вопрос

Можешь также вернуть ячейки одного из самых длинных путей, а не только его длину?

Решение

Проведите стрелку от каждой ячейки к каждому соседу со значением больше. Значения возрастают вдоль каждой стрелки, поэтому никакая цепочка стрелок не может вернуться туда, откуда началась: сетка — это ориентированный ациклический граф, а задача заключается в поиске его самого длинного пути. В общем графе ответ на этот вопрос невозможно найти для больших входных данных, но при отсутствии циклов самый длинный путь из ячейки зависит только от неё, поэтому его можно вычислить один раз для каждой ячейки, и сложность всей задачи снижается до O(m × n). Поиск в глубину с мемоизацией вычисляет его сверху вниз; последовательное удаление ячеек сетки, начиная с пиков, — алгоритм Кана в обратном порядке — вычисляет его снизу вверх.

Следуйте по каждому возрастающему пути

Верно, но не успевает на самых больших тестах

Идея

Начните обход из каждой ячейки. Из текущей ячейки попробуйте перейти к каждому из четырёх соседей со значением побольше, а затем продолжайте двигаться таким же образом, пока не останется соседей со значением побольше. Подсчитайте количество ячеек в каждом обходе и сохраните наибольшее количество.

Для обхода не нужен набор посещённых ячеек. Значения растут на каждом шаге, поэтому обход никогда не сможет вернуться в ячейку: чтобы снова оказаться в ней, ему пришлось бы вернуться к значению этой ячейки. Храните обходы в стеке записей (ячейка, длина). Извлечение записи завершает один обход в этой ячейке, а добавление её соседей со значениями побольше продолжает его.

Метод корректен, но безнадёжно медленный, потому что обходы ветвятся. В сетке 100 × 100, где значение каждой ячейки равно сумме её строки и столбца, каждый шаг вправо или вниз ведёт к большему значению, и только из верхней левой ячейки начинается более 10^58 обходов. Хуже того, обход из каждой ячейки выполняется заново каждый раз, когда через неё проходит другой обход, — именно эту расточительность устраняет следующий подход.

Алгоритм

Для каждой ячейки поместите в стек пару (эта ячейка, 1).
Извлеките запись (ячейка, длина) и обновите ответ, используя длину.
Для каждого соседа внутри сетки со строго большим значением поместите в стек пару (сосед, длина + 1).
Повторяйте, пока стек не опустеет, затем переходите к следующей начальной ячейке.
Верните наибольшую найденную длину.

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

Мемоизированный поиск в глубину с собственным стеком

Идея

Пусть best[cell] — количество ячеек в самом длинном возрастающем пути, который начинается в этой ячейке. Путь либо заканчивается прямо здесь, либо его следующий шаг ведёт к большему соседу, после чего путь продолжается по самому длинному пути от этого соседа. Поэтому best[cell] = 1 + max(best[nb]) для больших соседей nb, а если их нет, значение равно 1. Это можно безопасно использовать повторно благодаря ациклической структуре: ячейки перед cell на любом пути меньше неё, поэтому они никогда не могут появиться после неё, а лучшее продолжение от cell одинаково независимо от того, как ты к ней пришёл. Вычисли значение best для каждой ячейки один раз и сохрани его — экспоненциальное дерево обходов сведётся к одному посещению каждой ячейки.

В первом примере у 9 нет большего соседа, поэтому значение best для неё равно 1. Затем для 8 получается 2, для 7 — 3, для 6 и 2 — 4, для 5 и 1 — 5, для 4 — 6, а для 3 — 7 — это и есть ответ. Каждая ячейка проверяет 4 соседей, поэтому сложность составляет O(m × n).

Естественный вариант кода — рекурсивный: функция возвращает значение best для ячейки, вызывая себя для каждого большего соседа. Глубина вызовов равна длине пути, по которому она идёт, а ограничения допускают путь через каждую ячейку: значения, образующие зигзаги по сетке 100 × 100, создают путь из 10 000 ячеек, тогда как Python по умолчанию останавливается после 1 000 вложенных вызовов. Приведённый ниже код выполняет саму рекурсию, поэтому для него нет слишком длинных путей. Храни стек ячеек и для каждой ячейки — количество направлений из четырёх, которые ты уже проверил. Посмотри на верхнюю ячейку: если осталось направление, проверь его и добавь туда соседа в стек, если он больше и ещё не обработан. Когда проверены все четыре направления, все большие соседи уже обработаны, поэтому извлеки ячейку из стека и установи её значение best. Это в точности тот порядок, в котором выполнялись бы рекурсивные вызовы.

Для поиска не нужна отметка «в процессе», в отличие от поиска циклов. Каждая ячейка в стеке больше ячейки под ней, поэтому больший сосед верхней ячейки не может находиться ниже в стеке.

Алгоритм

Заполните best значением 0 (пока неизвестно) и задайте счётчик направлений, равный 0, для каждой ячейки.
Для каждой ячейки со значением best 0 поместите её в стек.
Посмотрите на верхнюю ячейку. Если для неё осталось направление, продвиньте её счётчик и поместите соседнюю ячейку в этом направлении в стек, если она находится внутри сетки, имеет большее значение и ещё не обработана.
Если проверены все четыре направления, извлеките ячейку из стека и задайте best значение на 1 больше наибольшего значения best среди соседних ячеек с большими значениями либо 1, если таких ячеек нет.
Верните наибольшее значение 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

Снимите сетку с её пиков

Идея

Перевернём динамическое программирование и будем строить его сверху вниз, начиная с наибольших значений, как алгоритм Кана строит топологический порядок. Назовём ячейку пиком, если ни один её сосед не больше неё. Путь от пика не может двигаться, поэтому состоит из 1 ячейки. Удалим сразу все пики: это слой 1. Теперь некоторые ячейки лишились последнего соседа с большим значением, поэтому они стали пиками среди оставшихся ячеек. Удалим их как слой 2 и продолжим, пока сетка не опустеет. Ответ — количество слоёв.

Почему это работает: ячейка попадает в слой k ровно тогда, когда самый длинный путь, начинающийся в ней, состоит из k ячеек. Ячейка удаляется в раунде после того, как исчезает её последний сосед с большим значением, поэтому её слой на 1 больше самого высокого слоя среди соседей с большими значениями — это та же формула best[cell] = 1 + max(best[nb]), что и в предыдущем подходе. Самому глубокому слою соответствует начало самого длинного пути.

В первом примере единственный пик — это 9 (его соседи — 8 и 2). После его удаления становится доступна 8, после удаления 8 — 7, после удаления 7 — 2 и 6, после удаления этих двух — 1 и 5, после удаления 5 — 4, а после удаления 4 — 3. Всего получается 7 слоёв, а путь 3, 4, 5, 6, 7, 8, 9 проходит через одну ячейку каждого слоя.

Чтобы быстро находить следующий слой, посчитай для каждой ячейки, сколько у неё осталось соседей с большими значениями. Удаление ячейки уменьшает счётчик каждого её соседа с меньшим значением; когда счётчик достигает 0, этот сосед попадает в следующий слой. Каждая ячейка удаляется один раз, а каждая пара соседей рассматривается постоянное число раз, поэтому трудоёмкость составляет O(m × n), без стека и рекурсии.

Алгоритм

Для каждой ячейки посчитайте соседей со значением больше.
Поместите в текущий слой каждую ячейку, у которой счётчик равен 0.
Пока слой не пуст, увеличивайте счётчик слоёв на 1. Для каждой ячейки в нём уменьшите счётчик каждого строго меньшего соседа и поместите в следующий слой соседа, счётчик которого достигнет 0.
Сделайте следующий слой текущим и повторите.
Верните количество слоёв.

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

Ловушки и крайние случаи

Ошибки здесь возникают из-за слова «строго», глубокой рекурсии и привычек, перенесённых из других задач на сетки.

Сравнение с >= вместо >. Если рядом стоят две 4, каждая из них считается шагом вверх относительно другой, стрелки образуют цикл, полный перебор ходит туда-сюда бесконечно, а поиск с мемоизацией считывает длину, вычисление которой ещё не завершено.
Рекурсия на очень длинных путях. Рекурсивный поиск углубляется на столько вызовов, какова длина пути, а ограничения допускают путь через каждую клетку: значения, змейкой проходящие туда-сюда по сетке 100 × 100, образуют путь из 10,000 клеток — в десять раз больше установленного по умолчанию в Python предела в 1,000 вложенных вызовов. Для таких длинных путей нужен итеративный поиск с собственным стеком или увеличенный предел рекурсии (sys.setrecursionlimit в Python), но слишком высокий предел всё равно может привести к переполнению собственного стека интерпретатора.
Пропуск уже посещённых клеток, как при заливке. Попасть в уже обработанную клетку — не тупик: её сохранённая длина — именно то, что нужно текущей клетке. Считайте её, не пропускайте.
Начало только с наименьшего значения. В первом примере от 1 получается путь из 5 клеток, но ответ, 7, начинается с 3. Самый длинный путь может начинаться в любой клетке, у которой нет меньшего соседа, а таких клеток может быть много.
Возврат 0. Каждая клетка сама по себе образует путь длиной 1, поэтому для сетки с одинаковыми значениями или сетки 1 × 1 ответ равен 1. Начинайте длину для каждой клетки с 1, а не с 0.
В подходе с послойным удалением уменьшение счётчика равного соседа. Только у строго меньшего соседа исчезает больший сосед.

Частые вопросы4

Какова временная сложность задачи «Наиболее длинный возрастающий путь в матрице»?

Время O(m × n) и память O(m × n) при мемоизированном поиске в глубину или топологическом удалении. Каждая из m × n ячеек обрабатывается один раз и проверяет 4 соседние ячейки постоянное число раз, а каждый метод хранит по одному числу для каждой ячейки. Перебор всех путей из каждой ячейки вместо этого требует экспоненциального времени: на сетке 100 × 100, где значение каждой ячейки равно сумме её строки и столбца, из верхнего левого угла выходит более 10^58 путей.

Почему для этой задачи не нужен набор посещённых узлов?

Путь, который движется только вверх, никогда не сможет вернуться в клетку, потому что для этого ему пришлось бы спуститься обратно к значению этой клетки. Поэтому правило строгого возрастания уже запрещает повторные посещения, и в графе шагов нет циклов. Именно поэтому мемоизация безопасна: клетки, расположенные перед данной клеткой, не могут повлиять на путь после неё.

Задача «Наибольший возрастающий путь в матрице» относится к динамическому программированию или к задачам на графы?

И то, и другое. Это самый длинный путь в ориентированном ациклическом графе, то есть динамическое программирование по топологическому порядку: ответ для ячейки равен 1 плюс наилучший ответ среди её соседей с большим значением. Поиск в глубину с мемоизацией заполняет таблицу в порядке завершения поиска для ячеек, а топологическое удаление вершин заполняет её слой за слоем, начиная с пиков. Сортировка ячеек по значению от большего к меньшему даёт третий допустимый порядок, ценой O(m × n × log(m × n)) на сортировку.

Чем это отличается от наибольшей возрастающей подпоследовательности?

Подпоследовательность может пропускать элементы и должна сохранять их порядок, тогда как здесь путь должен переходить в соседнюю клетку в одном из четырёх направлений. Задача о подпоследовательности — это динамическое программирование на прямой; эта задача — динамическое программирование на сетке, представленной в виде графа. Обе задачи опираются на один и тот же факт: строго возрастающая цепочка не может вернуться к самой себе по циклу.

Python

def longestIncreasingPath(matrix):
    # Напишите код здесь

Тестовые случаи

Случай 1

Случай 2

Случай 3

Ввод

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

Ожидается

Longest Increasing Path in a Matrix

Функция

Ограничения

Примеры

Подсказки

Решение

Следуйте по каждому возрастающему пути

Мемоизированный поиск в глубину с собственным стеком

Снимите сетку с её пиков

Ловушки и крайние случаи

Частые вопросы4

Похожие задачи