Самый длинный возрастающий путь в матрице

Дана матрица целых чисел. Найти самый длинный путь, в котором чисоа возастают.

Из каждой ячейки матрицы можно двигаться в 4 направлениях: вверх, вниз, влево, вправо. Нельзя двигаться диагонально или за пределы матриы (то есть выйдя за пределы матрицы в конце строки/столбца, вы не попадаете в начало следующей строки/столбца).

Пример 1:

Дано: nums = 
[
  [9,9,4],
  [6,6,8],
  [2,1,1]
] 
Результат: 4 
Пояснение: Самый длинный возрастающий путь состоит из значений [1, 2, 6, 9].

Пример 2:

Дано: nums = 
[
  [3,4,5],
  [3,2,6],
  [2,2,1]
] 
Результат: 4 
Пояснение: Самый длинный возрастающий путь состоит из значений [3, 4, 5, 6]. 

Идея решения 1 (DFS)

Мы должны применить поиск в глубину (DFS) для каждой ячейки. При этом будем кэшировать промежуточные результаты, чтобы не пересчитвать их повторно. Поскольку ячеек в матрице O(mn) и для каждой ячейки нам нужно поиском обойти все другие ячейки, то общая сложность алгоритма будет $O(m^2{n}^2)$.

Мы рекурсивно вызываем dfs(x, y) много рпаз, где (x, y) - это ячейка в строке x  и столбце y. Но если мы знаем результат для смежных ячеек, мы можем использовать его за констаное время. Если же какая-то ячейка ещё не посчитана, то мы ее считаем за O(mn).

Имплементация 

// DFS + Memoization Solution
public class Solution {
// направления движения из ячейки
    private static final int[][] dirs = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
    private int m, n;

    public int longestIncreasingPath(int[][] matrix) {
        if (matrix.length == 0) return 0; // проверка входных данных
        m = matrix.length; n = matrix[0].length;
        int[][] cache = new int[m][n]; // кэш
        int ans = 0; // здесь бедт финальный результат    
        // для каждой ячейки запускаем рекурсивно DFS
        for (int i = 0; i < m; ++i)
            for (int j = 0; j < n; ++j)
                // выбираем максимальный результат
                ans = Math.max(ans, dfs(matrix, i, j, cache));
        return ans;
    }
    // рекурсивная функция DFS
    private int dfs(int[][] matrix, int i, int j, int[][] cache) {
        // если для рассматриваемой ячейки мы уже посчитали результат,
        // то возвращаем его
        if (cache[i][j] != 0) return cache[i][j];
        // для каждого направления вычисляем координаты ячейки    
        // и если они не выходят за границы матрицы, 
        // то вызываем рекурсивно DFS 
        // и сравниваем с результатом кэша для этой ячейки,
        // и в кэш записываем наибольший результат
        for (int[] d : dirs) {
            // новая координата
            int x = i + d[0], y = j + d[1];
            // проверка коордтинат
            if (0 <= x && x < m && 0 <= y && y < n && matrix[x][y] > matrix[i][j])
                // рекурсия и сравнение с существующим результатом
                cache[i][j] = Math.max(cache[i][j], dfs(matrix, x, y, cache));
        }
        // возвращаем финальный кэш + 1
        return ++cache[i][j];
    }
} 

Идея решения 2 (BFS, очищение лука)

Определим самый длинный возрастающий путь из ячейки $(i,j),$ как функцию

$f(i, j)$$=max\{f(x,y)|(x,y)-это\; сосед\; ячейки(i,j)\mathrm{m}\mathrm{a}\mathrm{t}\mathrm{r}\mathrm{i}\mathrm{x}[x][y]>\mathrm{m}\mathrm{a}\mathrm{t}\mathrm{r}\mathrm{i}\mathrm{x}[i][j]\}+1$

Эта функция выглядит, как будто мы можем использовать динамическое программирование без DFS!

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

Пример: числа Фибоначчи.

$F(0) = 1, F(1) = 1, F(n) = F(n - 1) + F(n - 2)$

Задача $F(n)$ зависит от задачи для двух предыдущих чисел. Зависимый подсчитывается после тех, от кого зависит.

Такая зависимость назыаается топологическим порядком (Topological order) или топологической сортировкой (Topological sorting):

Топологическая сортировка для направленного ацикличного графа (Directed Acyclic Graph - DAG) - это линейная сортировка вершин таким образом, что в каждом направленном ребре $(u,v)$, вершина $u$ идет перед вершиной $v$ в отсортированном порядке (по возрастанию или убыванию).

В посталенной задаче нет условий для топологической сортировки. Нужно ввести дополнительную структуру, чтобы её задать.

Мы предлагаем рассмотреть структуру, которая похожа на "очистку лука". Мы определим ячейки матрицы, вокруг которых нет других с бОльшим значением, как "листья" нашего графа. Эти чейки "доминируют" (некоторых) своих соседей. И тогда обнуляя эти ячейки, мы высвобождаем новые листья. Обнуляя эти новые листья, мы выявляем новые листья. Пока не обнулится вся матрица. И этот процесс похож на то, как происходит очистка лука.

Длина пути будет равна количеству слоёв нашего "лука".

Имплементация

// Topological Sort Based Solution
public class Solution {
    private static final int[][] dir = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
    private int m, n;
    public int longestIncreasingPath(int[][] grid) {
        int m = grid.length;
        if (m == 0) return 0;
        int n = grid[0].length;
        // создаем пустую матрицу размером с исходной и с дополнительными "полями"
        // на полях 0, если в исходной матрице все положительные числа,
        // или INT_MIN, если есть отрицательные
        int[][] matrix = new int[m + 2][n + 2];

        // копируем исходную матрицу в эту вспомогательную
        for (int i = 0; i < m; ++i)
            System.arraycopy(grid[i], 0, matrix[i + 1], 1, n);

        // считаем outdegrees для каждой ячейки (x,y)
        // то есть сколько бОльших элементов окружают ячейку
        int[][] outdegree = new int[m + 2][n + 2];
        for (int i = 1; i <= m; ++i)
            for (int j = 1; j <= n; ++j)
                for (int[] d: dir)
                    if (matrix[i][j] < matrix[i + d[0]][j + d[1]])
                        outdegree[i][j]++;

        // элементы, которые "доминируют" соседей, но не доминируемы больше ничем,
        // будут иметь outdegree=0 - это внешний слой "лука"
        n += 2;
        m += 2;
        List<int[]> leaves = new ArrayList<>();
        for (int i = 1; i < m - 1; ++i)
            for (int j = 1; j < n - 1; ++j)
                // добавляем "внешний слой лука" в очередь leaves
                if (outdegree[i][j] == 0) leaves.add(new int[]{i, j});

        int height = 0; // считаем, сколько у "лука" слоев
        while (!leaves.isEmpty()) {
            height++; //  если очередь не пуста, то +1 к количеству слоёв

            // Убираем элемент из очереди, 
            // уменьшаем на 1 outgegree тех элементов, которые он доминирует
            // если у номинируемого элемента outdegree==0, 
            // то его больше ничто не доминирует, добавляем его в очередь
            List<int[]> newLeaves = new ArrayList<>();
            for (int[] node : leaves) {
                for (int[] d:dir) {
                    int x = node[0] + d[0], y = node[1] + d[1];
                    if (matrix[node[0]][node[1]] > matrix[x][y])
                        if (--outdegree[x][y] == 0) // ничего не доминирует больше
                            newLeaves.add(new int[]{x, y});
                }
            }
            // обновляем очередь
            leaves = newLeaves;
        }
        // возвращаем количество насчитанных слоев
        return height;
    }
}