LeetCode329.矩阵中的最长递增路径

原题链接：矩阵中的最长递增路径

题目描述

• 给定一个整数矩阵，找出最长递增路径的长度。
• 对于每个单元格，你可以往上，下，左，右四个方向移动。 你不能在对角线方向上移动或移动到边界外（即不允许环绕）。

示例 1

输入:

[
  [9,9,4],
  [6,6,8],
  [2,1,1]
] 

输出: 4
解释: 最长递增路径为[1, 2, 6, 9]。

示例 2

输入：

[
  [3,4,5],
  [3,2,6],
  [2,2,1]
]

输出: 4
解释: 最长递增路径是[3, 4, 5, 6]。

思路描述

核心——DFS、DP

1. 首先需要一个dfs方法。以向左递归为例，如果matrix[i-1][j]<=matrix[i][j]则返回0；否则继续向四个方向递归。dfs方法需要判断边界。
2. 然后需要一个跟matrix一样大的二维数组int[][] dp，记录已经计算出来的每一个点的最长递增路径，防止重复计算。
3. 外层双重循环遍历所有的点，并比较每个点的dfs方法返回值，得到最大值。

class Solution {
    public int longestIncreasingPath(int[][] matrix) {
        if (matrix.length == 0) {
            return 0;
        }
        int[][] dp = new int[matrix.length][matrix[0].length];;
        int max = 0;

        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[i].length; j++) {
                max = Math.max(max, dfs(matrix, dp, i, j, Integer.MIN_VALUE));
            }
        }
        return max;
    }

    private int dfs(int[][] matrix, int[][] dp, int i, int j, int preVal) {
        // 边界判断
        if (i < 0 || j < 0 || i > matrix.length - 1 || j > matrix[i].length - 1) {
            return 0;
        }
        // 是否递增判断
        if (matrix[i][j] <= preVal) {
            return 0;
        }
        // 如果该点已经判断过，则直接返回结果
        if (dp[i][j] != 0) {
            return dp[i][j];
        }

        // 递归上下左右四个点的值
        int left = dfs(matrix, dp, i - 1, j, matrix[i][j]);
        int right = dfs(matrix, dp, i + 1, j, matrix[i][j]);
        int up = dfs(matrix, dp, i, j - 1, matrix[i][j]);
        int down = dfs(matrix, dp, i, j + 1, matrix[i][j]);

        // 状态转移方程为dp[i][j] = 1 + Max(left, right, up, down)
        dp[i][j] = 1 + Math.max(Math.max(left, right), Math.max(up, down));
        return dp[i][j];
    }
}

一年又一年，字节跳动 Lark（飞书） 研发团队又双叒叕开始招新生啦！

【内推码】：GTPUVBA

【内推链接】：https://job.toutiao.com/s/JRupWVj

【招生对象】：20年9月后~21年8月前 毕业的同学

【报名时间】：6.16-7.16（提前批简历投递只有一个月抓住机会哦！）

【画重点】：提前批和正式秋招不矛盾！面试成功，提前锁定Offer；若有失利，额外获得一次面试机会，正式秋招开启后还可再次投递。