方法：dfs（深度优先搜索）

既然是查找最长的递增路径长度，那我们首先要找到这个路径的起点，起点不好直接找到，就从上到下从左到右遍历矩阵的每个元素。然后以每个元素都可以作为起点查找它能到达的最长递增路径。

如何查找以某个点为起点的最长递增路径呢？我们可以考虑深度优先搜索，因为我们查找递增路径的时候，每次选中路径一个点，然后找到与该点相邻的递增位置，相当于进入这个相邻的点，继续查找递增路径，这就是递归的子问题。因此递归过程如下：

  • 终止条件： 进入路径最后一个点后，四个方向要么是矩阵边界，要么没有递增的位置，路径不能再增长，返回上一级。
  • 返回值： 每次返回的就是本级之后的子问题中查找到的路径长度加上本级的长度。
  • 本级任务： 每次进入一级子问题，先初始化后续路径长度为0，然后遍历四个方向（可以用数组表示，下标对数组元素的加减表示去往四个方向），进入符合不是边界且在递增的邻近位置作为子问题，查找子问题中的递增路径长度。因为有四个方向，所以最多有四种递增路径情况，因此要维护当级子问题的最大值。

具体做法：

  • step 1：使用一个dp数组记录(i , j)处的单元格拥有的最长递增路径，这样在递归过程中如果访问到就不需要重复访问。
  • step 2：遍历矩阵每个位置，都可以作为起点，并维护一个最大的路径长度的值。
  • step 3：对于每个起点，使用dfs查找最长的递增路径：只要下一个位置比当前的位置数字大，就可以深入，同时累加路径长度。

时间复杂度：o(nm)

空间复杂度：o(mn)

class Solution {
  public:
    int solve(vector<vector<int> >& matrix) {
        n = matrix.size();
        m = matrix[0].size();

        vector<int> temp(m, 0);
        //用来统计各个数字作为起点的最长路径长度
        vector<vector<int> > count;
        for (int i = 0; i < n; i++)
            count.push_back(temp);

        int res = 0;
	  	//遍历所有元素作为起点
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                res = max(res, dfs(matrix, count, i, j));
            }
        }

        return res;
    }
  private:
    int n;
    int m;
    int next[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
    int dfs(vector<vector<int> >& matrix, vector<vector<int> >& count, int i,
            int j) {
        if (count[i][j])
            return count[i][j];
        count[i][j]++;

        for (int idx = 0; idx < 4; idx++) {
            int next_i = i + next[idx][0];
            int next_j = j + next[idx][1];
			//满足条件进入递归
            if (next_i >= 0 && next_i < n && next_j >= 0 && next_j < m &&
                    matrix[next_i][next_j] > matrix[i][j]) {
                count[i][j] = max(count[i][j], dfs(matrix, count, next_i, next_j) + 1);
            }
        }
        return count[i][j];
    }
};