Рекурсия Длинный путь увеличения в матрице - PullRequest
Новая
       19

Рекурсия Длинный путь увеличения в матрице

0 голосов
/ 10 ноября 2019

Я реализую проблему длинного растущего пути кода leetcode.

Учитывая целочисленную матрицу, найдите длину самого длинного растущего пути.

Из каждой ячейки вы можете двигаться в четырех направлениях. : влево, вправо, вверх или вниз. Вы НЕ МОЖЕТЕ двигаться по диагонали или выходить за пределы границы (т. Е. Обход не допускается).

Пример 1:

Ввод: nums = [[9,9,4], [6,6,8], [2,1,1]] Вывод: 4 Объяснение: Самый длинный увеличивающийся путь - [1, 2, 6, 9].

Итак, ниже моя реализация много пробуетрекурсия, но не в состоянии понять, почему он не дает правильного результата, почему maxDist в этом примере уменьшается с 4 до 3 до 2, поскольку эта переменная является глобальной, а не локальной.

открытый класс LongestIncreasingPath {

private static final int[][] dirs = { { 0, 1 }, { 1, 0 }, { 0, -1 }, { -1, 0 } };
private int m, n;
int maxDist;

public int longestIncreasingPath(int[][] matrix) {
    if (matrix.length == 0)
        return 0;
    m = matrix.length;
    n = matrix[0].length;
    int ans = 1;
    for (int i = 0; i < m; ++i)
        for (int j = 0; j < n; ++j) {
            dfs(matrix, i, j, 1);
            ans = Math.max(ans, maxDist);
        }
    return ans;
}
private int dfs(int[][] matrix, int i, int j, int dist) {
    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]) {
            maxDist = Math.max(maxDist, dfs(matrix, x, y, dist+1));
        }
    }
    return dist;
}

public static void main(String[] args) {
    int[][] nums = { { 9, 9, 4 }, { 6, 6, 8 }, { 2, 1, 1 } };
    LongestIncreasingPath lIP = new LongestIncreasingPath();
    System.out.println(lIP.longestIncreasingPath(nums));
}

}

...