【困难】矩阵最长递增路径 (递归缓存优化)

先看题目

给定一个二维数组 matrix ，可以从任何位置出发，每一步可以向上、下、左、右四个方向移动，返回最大递增路径长度。
例子：
matrix =
 6 5 4
 1 2 3
 2 7 1
从第二行的 1 出发可形成路径 1 2 3 4 5 6 ，为最长的路径，则答案返回 6.

这道题主要考验的就是递归思路，其实还是相对容易想出来的，我们这样定义一个函数 f(i,j) 含义为获取从 i,j 位置出发所能得到的最大递增路径长度。ok 有了这层定义代码就很好出了如下。

public class Question5 {


    public static void main(String[] args) {
        int[][] matrix = new int[][]{{6, 5, 4}, {1, 2, 3}, {2, 7, 1}};

        System.out.println(longestIncreasingPath(matrix));
    }

    public static int longestIncreasingPath(int[][] matrix) {
        int maxLength = 0;
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[0].length; j++) {
                int length = process(i, j, matrix);
                if (maxLength < length) {
                    maxLength = length;
                }
            }
        }
        return maxLength;
    }

    

    public static int process(int i, int j, int[][] matrix) {

        if (i < 0 || j < 0 || i > matrix.length || j > matrix[0].length) {
            return 0;
        }
        int up = 1;
        int down = 1;
        int left = 1;
        int right = 1;

        if (j - 1 >= 0 && matrix[i][j - 1] > matrix[i][j]) {
            up += process(i, j - 1, matrix);
        }
        if (j + 1 < matrix[0].length && matrix[i][j + 1] > matrix[i][j]) {
            down += process(i, j + 1, matrix);
        }
        if (i - 1 >= 0 && matrix[i - 1][j] > matrix[i][j]) {
            left += process(i - 1, j, matrix);
        }
        if (i + 1 < matrix.length && matrix[i + 1][j] > matrix[i][j]) {
            right += process(i + 1, j, matrix);
        }

        return Math.max(Math.max(up, down), Math.max(left, right));
    }


}

在这一版中我们实现了基本的功能，但是时间复杂度上是存在问题的，最外层的双层循环的复杂度就已经达到 O(m*n) 了在乘以递归的复杂度就是很大的量级。

我们思考在递归上进行优化，不难发现我们在多次递归的过程中有很多数据是可以重复利用的，那么加个缓存就是一个很好的方案。

优化后的代码如下

public class Question5 {

    // 增加缓存
    public static int[][] cache;

    public static void main(String[] args) {
        int[][] matrix = new int[][]{{6, 5, 4}, {1, 2, 3}, {2, 7, 1}};

        System.out.println(longestIncreasingPath(matrix));
    }

    public static int longestIncreasingPath(int[][] matrix) {
        int maxLength = 0;
        cache = new int[matrix.length][matrix[0].length];
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[0].length; j++) {
                int length = process(i, j, matrix);
                if (maxLength < length) {
                    maxLength = length;
                }
            }
        }
        return maxLength;
    }

    

    public static int process(int i, int j, int[][] matrix) {

        if (i < 0 || j < 0 || i > matrix.length || j > matrix[0].length) {
            return 0;
        }
        if (cache[i][j] != 0) {
            return cache[i][j];
        }
        int up = 1;
        int down = 1;
        int left = 1;
        int right = 1;

        if (j - 1 >= 0 && matrix[i][j - 1] > matrix[i][j]) {
            up += process(i, j - 1, matrix);
        }
        if (j + 1 < matrix[0].length && matrix[i][j + 1] > matrix[i][j]) {
            down += process(i, j + 1, matrix);
        }
        if (i - 1 >= 0 && matrix[i - 1][j] > matrix[i][j]) {
            left += process(i - 1, j, matrix);
        }
        if (i + 1 < matrix.length && matrix[i + 1][j] > matrix[i][j]) {
            right += process(i + 1, j, matrix);
        }

        int max = Math.max(Math.max(up, down), Math.max(left, right));
        cache[i][j]=max;
        return max;
    }


}

加缓存的思想其实是我们日常开发中查询性能优化的常用手段了，所以说算法思想对与我们日常开发具备指导性的意义。

以上优化后时间复杂度为 O(m*n) 递归行为被缓存优化为常数基本了，在时间复杂度上以上即为最优解。

leecode 对应题目 矩阵中的最长递增路径