题解 | #矩阵最长递增路径#

这里访问过的结点就不会再访问，不满足大小关系！！一开始还傻乎乎使用visited记录访问过的结点

然后每次递归，终止条件是没法再向四周移动，每一层向上一层返回当前能够前进的最大长度

class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 递增路径的最大长度
     * @param matrix int整型vector<vector<>> 描述矩阵的每个数
     * @return int整型
     */
  //  走过的结点不会再走，因为不满足大小关系了，无需使用visited数组记录
    int solve(vector<vector<int> >& matrix) {
      int res = 1;
      int count = 0;
      int size = matrix.size();
      //  std::vector<std::vector<int>> dp(size, std::vector<int>(size, 0));
      //  不需要dp，每次每个结点只返回最大路径长度，各节点之间的最大路径长度没关联
      
      for (int i = 0; i < size; ++i) {
        for (int j = 0; j < size; ++j) {
          count = 0;
          res = std::max(res, recursion(matrix, size, i, j, count));
        }
      }
      
      return res;
    }
  private:
    //  返回给上一层当前的最大长度
    int recursion(std::vector<std::vector<int>> &matrix, const int &size, int i, int j, int &count) {
      //  上下左右
      int len = 0;
      
      if (i > 0 && matrix[i - 1][j] > matrix[i][j]) {
        len = std::max(len, recursion(matrix, size, i - 1, j, count));
      }
      
      if (i < size - 1 && matrix[i + 1][j] > matrix[i][j]) {
        len = std::max(len, recursion(matrix, size, i + 1, j, count));
      }
      
      if (j > 0 && matrix[i][j - 1] > matrix[i][j]) {
        len = std::max(len, recursion(matrix, size, i, j - 1, count));
      }
      
      if (j < size - 1 && matrix[i][j + 1] > matrix[i][j]) {
        len = std::max(len, recursion(matrix, size, i, j + 1, count));
      }
      
      count = len + 1;
      
      return count;
    }
};