题解 | 矩阵最长递增路径

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 递增路径的最大长度
     * @param matrix int整型vector<vector<>> 描述矩阵的每个数
     * @return int整型
     */
    int m, n;
    vector<vector<int>> f, w;
    int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};

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

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