矩阵中的最长递增路径

/*
 * 思路：
 * 1. 我们依旧定义一个方向数组dirs，表示四个可能的方向。
 * 2. 使用一个记忆化的二维数组dp，其中dp[i][j]表示以matrix[i][j]为起点的最长递增路径的长度。
 * 3. 对于每个单元格(i, j)，使用深度优先搜索（DFS）来找到以它为起点的最长递增路径。
 * 4. 在DFS过程中，如果移动后的值大于当前值，递归计算移动后的单元格的最长递增路径长度，并更新dp[i][j]。
 * 5. 最后遍历dp数组，找到最大的值即为答案。
 */

import java.util.Arrays;
import java.util.stream.IntStream;

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 == null || matrix.length == 0 || matrix[0].length == 0) {
            return 0;
        }
        m = matrix.length;
        n = matrix[0].length;
        int[][] dp = new int[m][n];
        return IntStream.range(0, m)
            .flatMap(i -> IntStream.range(0, n)
            .map(j -> dfs(matrix, i, j, dp)))
            .max()
            .orElse(0);
    }

    private int dfs(int[][] matrix, int i, int j, int[][] dp) {
        if (dp[i][j] != 0) {
            return dp[i][j];
        }
        int max = 1;
        for (int[] dir : dirs) {
            int x = i + dir[0], y = j + dir[1];
            if (x >= 0 && x < m && y >= 0 && y < n && matrix[x][y] > matrix[i][j]) {
                max = Math.max(max, 1 + dfs(matrix, x, y, dp));
            }
        }
        dp[i][j] = max;
        return max;
    }
}