Самый длинный возрастающий путь в матрице
Дана матрица целых чисел. Найти самый длинный путь, в котором чисоа возастают. Из каждой ячейки матрицы можно двигаться в 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...