题目描述

给定一个整数矩阵，请找到最长的上升路径。

对于矩阵中的每个格子，你每次可以走到上下左右四个方向，不能斜着走，也不能走出边界。

样例1

输入：nums = 
[
  [9,9,4],
  [6,6,8],
  [2,1,1]
] 
输出：4 
解释：最长的上升路径是：[1, 2, 6, 9].

样例2

输入：nums = 
[
  [3,4,5],
  [3,2,6],
  [2,2,1]
] 
输出：4 
解释：最长的上升路径是：[3, 4, 5, 6]. 不能斜着走。

算法

(记忆化搜索，动态规划) $O(n^2)$

这是动态规划里非常经典的一道题目，几乎是所有学编程的同学都会遇到的一道题目。

假设我们从最低点开始走，每次只能往更高的格子走。
状态表示：f[i][j]表示走到(i,j)这个格子时的最大长度。
状态转移：枚举上下左右四个格子，如果某个格子(a,b)比当前格子低，则用该格子更新当前格子的最大长度：f[i][j] = max(f[i][j], dp(a, b) + 1)。

由于这道题目的状态依赖关系比较复杂，不容易用循环来求每个状态的值，所以可以用记忆化搜索来做：如果某个状态还没计算过，则递归计算该状态的值。

时间复杂度分析：假设矩阵的边长是 $n$。则总共有 $n^2$ 个状态，状态转移的计算量是常数，所以总时间复杂度是 $O(n^2)$。

C++ 代码

class Solution {
public:
    int n, m;
    vector<vector<int>> f, g;
    int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};

    int dp(int x, int y)
    {
        if (f[x][y] != -1) return f[x][y];
        f[x][y] = 1;
        for (int i = 0; i < 4; i ++ )
        {
            int a = x + dx[i], b = y + dy[i];
            if (a >= 0 && a < n && b >= 0 && b < m && g[a][b] < g[x][y])
                f[x][y] = max(f[x][y], dp(a, b) + 1);
        }
        return f[x][y];
    }

    int longestIncreasingPath(vector<vector<int>>& matrix) {
        if (matrix.empty()) return 0;
        g = matrix;
        n = g.size(), m = g[0].size();
        f = vector<vector<int>>(n, vector<int>(m, -1));
        int res = 0;
        for (int i = 0; i < n; i ++ )
            for (int j = 0; j < m; j ++ )
                res = max(res, dp(i, j));
        return res;
    }
};