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

缺乏、安全感 2022-09-14 01:53 180阅读 0赞

#### 矩阵最长递增路径 ####

先看题目

给定一个二维数组 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;
        }
    
    
    }

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

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

leecode 对应题目 [矩阵中的最长递增路径][Link 1]

[Link 1]: https://leetcode-cn.com/problems/longest-increasing-path-in-a-matrix/submissions/