描述

• 给定一个n行m列矩阵 matrix，矩阵内所有数均为非负整数。
  求一条路径，该路径上所有数是递增的。
  这个路径必须满足以下条件：

  1. 对于每个单元格，你可以往上，下，左，右四个方向移动。 你不能在对角线方向上移动或移动到边界外。
  2. 你不能走重复的单元格。即每个格子最多只能走一次。

• 数据范围：

  
  

方法一

思路

• 深度优先搜索;

• 题目要求找出矩阵中最长递增路径，然而却没有指定路径的开始节点，所以需要遍历所有的节点，以每一个节点为头结点找出最长的递增路径；

• 假设指定头结点为(row,col)，那么从这个节点开始的下一步有以下四中走法：
  
  
  
  当然需要判断是否越过边界了以及下一步的值是大于点(row,col)的值的；

• 通过上述的走法可以得出如下递推公式：
  

• 代码如下：

  import java.util.*;
  public class Solution {
  /**
   * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
   * 递增路径的最大长度
   * @param matrix int整型二维数组 描述矩阵的每个数
   * @return int整型
   */
  public int solve (int[][] matrix) {
      int max = 0;
      if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
          return max;
      }
      // 以所有的节点为路径的开始节点
      for (int i = 0;i < matrix.length;++i){
          for (int j = 0;j < matrix[0].length;++j){
              // 计算从（i，j）开始的最长递增路径
              int temp = searchMaxPath(matrix,i,j,-1);
              max = Math.max(temp,max);
          }
      }
      return max;
  }
  // 计算以点（row，col）为路径头结点的最长递增路径
  private int searchMaxPath(int[][] matrix,int row,int col,int pre){
      if (row < 0 || col < 0 || 
          row >= matrix.length || col >= matrix.length){
          return 0;
      }
      if (matrix[row][col] <= pre){
          return 0;
      }
  
      int max = 0;
      int temp = 0;
      // 点（row，col）往上走的最长路径
      temp = searchMaxPath(matrix,row-1,col,matrix[row][col]);
      max = Math.max(temp,max);
      // 点（row，col）往下走的最长路径
      temp = searchMaxPath(matrix,row+1,col,matrix[row][col]);
      max = Math.max(temp,max);
      // 点（row，col）往左走的最长路径
      temp = searchMaxPath(matrix,row,col-1,matrix[row][col]);
      max = Math.max(temp,max);
      // 点（row，col）往右走的最长路径
      temp = searchMaxPath(matrix,row,col+1,matrix[row][col]);
      max = Math.max(temp,max);
  
      return max+1;
  }
  }

• 时间复杂度：，双重循环为mn，而dfs最坏情况为4^mn；

• 空间复杂度：，递归调用的深度不会超过mn。

方法二

思路

• 深度优先，记忆表；
• 方法一的时间复杂度过大，在处理大量数据时会比较吃力，所以需要考虑降低其时间复杂度；
• 我们知道在方法一中计算以点(row,col)为头结点时，其下一步最多会有四种走法(row_next,col_next)，且需要求出以(row_next,col_next)为头结点的最长递增路径，可以发现这之间是存在很多的重复计算的，毕竟一个节点是可能被多条路径所经过的；
• 所以我们可以考虑使用一个矩阵（记忆表）来记录以当前节点为头结点的最长递增路径，这样子当某一节点的路径经过已记录的节点时，就可以直接从矩阵中拿出已经记录的数据，而无需再次计算。
• 代码如下：

  import java.util.*;
  public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 递增路径的最大长度
     * @param matrix int整型二维数组 描述矩阵的每个数
     * @return int整型
     */
    // 记忆表
    private int[][] paths;
    public int solve (int[][] matrix) {
        int max = 0;
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return max;
        }
        // 初始化
        paths = new int[matrix.length][matrix[0].length];
        // 以所有的节点为路径的开始节点
        for (int i = 0;i < matrix.length;++i){
            for (int j = 0;j < matrix[0].length;++j){
                // 计算从（i，j）开始的最长递增路径
                int temp = searchMaxPath(matrix,i,j,-1);
                max = Math.max(temp,max);
            }
        }
        return max;
    }
    private int searchMaxPath(int[][] matrix,int row,int col,int pre){
        if (row < 0 || col < 0 || 
          row >= matrix.length || col >= matrix.length){
          return 0;
        }
        if (matrix[row][col] <= pre){
            return 0;
        }
        // 表中存在，直接返回
        if (paths[row][col] > 0){
            return paths[row][col];
        }
        int max = 0;
        int temp = 0;
        // 点（row，col）往上走的最长路径
        temp = searchMaxPath(matrix,row-1,col,matrix[row][col]);
        max = Math.max(temp,max);
        // 点（row，col）往下走的最长路径
        temp = searchMaxPath(matrix,row+1,col,matrix[row][col]);
        max = Math.max(temp,max);
        // 点（row，col）往左走的最长路径
        temp = searchMaxPath(matrix,row,col-1,matrix[row][col]);
        max = Math.max(temp,max);
        // 点（row，col）往右走的最长路径
        temp = searchMaxPath(matrix,row,col+1,matrix[row][col]);
        max = Math.max(temp,max);
        // 记录
        paths[row][col] = max + 1;
        return paths[row][col];
    }
  }

• 时间复杂度：,双重循环为mn，而dfs近乎；
• 空间复杂度：，递归深度不超过mn，记忆表大小为mn。