【困难】矩阵最长递增路径 (递归缓存优化)-蒲公英云

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

矩阵最长递增路径

先看题目

给定一个二维数组 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;
    }
    /** * 定义这样一个递归 f(i,j) 从 i,j 位置出发返回最长递增路径长度 */
    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;
    }
    /** * 定义这样一个递归 f(i,j) 从 i,j 位置出发返回最长递增路径长度 */
    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;
    }
}