329. Longest Increasing Path in a Matrix

https://leetcode.com/problems/longest-increasing-path-in-a-matrix/description/

矩阵里找最长的递增路径，二维走格+ longest increasing => DP。DFS + memorization的方法很直观，dp[i][j]存下(i, j)对应的最长路径，检查一下四周看加上它最长能有多远，每个元素只会遍历一次，时间复杂度O(MN)。递推DP有点tricky, 顺序遍历的话对(i, j)并不知道(i +1, j)和(i, j+1)的值。它的状态变化除了表面上的从四周跳转过来，实质上是倒着从数大到小跳过来，最大的值长度只能是1，第二大的值长度最多为2，依次类推。

/*
 * @lc app=leetcode id=329 lang=cpp
 *
 * [329] Longest Increasing Path in a Matrix
 */
class Solution {
public:
    int longestIncreasingPath(vector<vector<int>>& matrix) {
        const int M = matrix.size(), N = M == 0 ? 0 : matrix[0].size();
        if (M == 0 || N == 0) return 0;
        vector<vector<int>> m;
        for (int i = 0; i < M; ++i) {
            for (int j = 0; j < N; ++j) {
                m.push_back({matrix[i][j], i, j});
            }
        }
        sort(m.begin(), m.end(), [](const auto &a, const auto &b) {
            return a[0] > b[0];
        });
        vector<vector<int>> dirs = {{0, -1}, {0, 1}, {-1, 0}, {1, 0}};
        vector<vector<int>> dp(M, vector<int>(N, 1));
        int res = 0;
        for (const auto &e : m) {
            const int i = e[1], j = e[2];
            for (const auto &dir : dirs) {
                const int x = i + dir[0];
                const int y = j + dir[1];
                if (x >= 0 && x < M && y >= 0 && y < N && matrix[x][y] > matrix[i][j]) {
                    dp[i][j] = max(dp[i][j], dp[x][y] + 1);
                }
            }
            res = max(res, dp[i][j]);
        }
        return res;
    }
};