题目

给定一个整数矩阵，找出最长递增路径的长度。

对于每个单元格，你可以往上，下，左，右四个方向移动。你不能在对角线方向上移动或移动到边界外（即不允许环绕）。

示例 1:

1
2
3
4
5
6
7
8


输入: nums = 
[
  [9,9,4],
  [6,6,8],
  [2,1,1]
] 
输出: 4 
解释: 最长递增路径为 [1, 2, 6, 9]。

示例 2:

1
2
3
4
5
6
7
8


输入: nums = 
[
  [3,4,5],
  [3,2,6],
  [2,2,1]
] 
输出: 4 
解释: 最长递增路径是 [3, 4, 5, 6]。注意不允许在对角线方向上移动。

题解

一开始看到这道题是懵逼的，感觉很难的样子，主要是这个是个矩阵，而之前数组最大上升子序列之类的题目都只是一个数组，一维的，而这一下子换成了二维的，就不知道该怎么做了。

后来想了下，发现改为二维后，问题并不大，依旧是遍历就行了。这道题是动态规划，求最大递增序列的长度，状态转移方程也比较好想。我们假设dp[i][j]数组中存储的是当前节点的最大递增序列的长度。那么转移方程为：

1
2
3
4
5


dp[i][j] = max(dp[i][j + 1] + 1, 
               dp[i][j - 1] + 1,
               dp[i + 1][j] + 1,
               dp[i - 1][j] + 1
              )

而整个矩阵的最大长度就是求最大的dp[i][j]值。基于这个方程，很快就写出了下面的程序，然而它是错误的。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26


int longestIncreasingPath(vector<vector<int>>& matrix) {
    if (matrix.empty()) return 0;
    int max_len = 0;
    vector<vector<int>> dp(matrix.size(), vector<int>(matrix[0].size(), 1));

    for (int i = 0; i < matrix.size();i++) {
        for (int j = 0;j < matrix[i].size();j++) {
            if (j != 0 && matrix[i][j] > matrix[i][j - 1]) {
                dp[i][j] = max(dp[i][j - 1] + 1, dp[i][j]);
            }
            if (j != matrix[i].size() - 1 && matrix[i][j] > matrix[i][j + 1]) {
            }
            if (i != 0 && matrix[i][j] > matrix[i - 1][j]) {
                dp[i][j] = max(dp[i - 1][j] + 1, dp[i][j]);
            }
            if (i != matrix.size() - 1 && matrix[i][j] > matrix[i + 1][j]) {
                dp[i][j] = max(dp[i + 1][j] + 1, dp[i][j]);
            }

            max_len = max(max_len, dp[i][j]);
        }
    }

    return max_len;
}

以下面的例子说下上面实现的错误原因。

1
2
3
4
5


vv = {
    { 9, 9, 4 },
    { 6, 6, 8 },
    { 2, 1, 1 }
};

例子中的最大长度序列是1, 2, 6, 9，按照我们的状态转移方程，我们期待的方式是，dp[2][1] = 1，dp[2][0] = 2, dp[1][0], = 3, dp[0][0] = 4。但上面的程序中在dp[0][0]这里便会出错，因为这个时候dp[1][0]是1，所以dp[0][0]为2，结果显然不对。

明白了错误原因后，发现自底向上不好写，因此改为了递归，改为递归后发现就是一个深度优先遍历。实现如下：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54


int recursive(vector<vector<int>> &matrix, int i, int j, vector<vector<int>> &vv) {
    //int tmp = 0;
    if (j != 0 && matrix[i][j] > matrix[i][j - 1]) {
        if (vv[i][j - 1] == 0) {
            vv[i][j] = max(vv[i][j], recursive(matrix, i, j - 1, vv) + 1);
        }
        else {
            vv[i][j] = max(vv[i][j], vv[i][j - 1] + 1);
        }
    }
    if (j != matrix[i].size() - 1 && matrix[i][j] > matrix[i][j + 1]) {
        if (vv[i][j + 1] == 0) {
            vv[i][j] = max(vv[i][j], recursive(matrix, i, j + 1, vv) + 1);
        }
        else {
            vv[i][j] = max(vv[i][j], vv[i][j + 1] + 1);
        }
    }
    if (i != 0 && matrix[i][j] > matrix[i - 1][j]) {
        if (vv[i - 1][j] == 0) {
            vv[i][j] = max(vv[i][j], recursive(matrix, i - 1, j, vv) + 1);
        }
        else {
            vv[i][j] = max(vv[i][j], vv[i - 1][j] + 1);
        }
    }
    if (i != matrix.size() - 1 && matrix[i][j] > matrix[i + 1][j]) {
        if (vv[i + 1][j] == 0) {
            vv[i][j] = max(vv[i][j], recursive(matrix, i + 1, j, vv) + 1);
        }
        else {
            vv[i][j] = max(vv[i][j], vv[i + 1][j] + 1);
        }
    }

    if (vv[i][j] == 0)
        vv[i][j] = 1;

    return vv[i][j];
}

int longestIncreasingPath(vector<vector<int>>& matrix) {
   if (matrix.empty()) return 0;
   int max_count = 0;
   vector<vector<int>> dp(matrix.size(), vector<int>(matrix[0].size(), 0));

   for (int i = 0; i < matrix.size(); i++) {
       for (int j = 0; j < matrix[i].size(); j++) {
           max_count = max(max_count, recursive(matrix, i, j, dp));
       }
   }

   return max_count;
}

recursive函数用来递归搜索当前节点的最大递增序列的长度，而在longestIncreasingPath函数中则遍历整个矩阵，查找以矩阵所有节点为起始节点的值的最长递增序列的长度，而这些长度中的最大那个值便是我们要求的那个值。

当然，自己的实现略微有些复杂了，查看讨论后，发现可以精简一下，这里就不精简了。