题解 | 矩阵最长递增路径

#include <vector>
class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 递增路径的最大长度
     * @param matrix int整型vector<vector<>> 描述矩阵的每个数
     * @return int整型
     */

    int ans = 0;  //final answer
    int res = 0;  //recorde the maxlength from one position
    vector< vector<int>> memo;  //0表示没有访问，其他表示从i，j出发的最大长度

    int solve(vector<vector<int> >& matrix) {
        memo.resize(matrix.size(), vector<int>(matrix[0].size(),
                                               0));  //先把大小确定了，再填值；
        for (int i = 0; i < matrix.size(); i++) {
            for (int j = 0; j < matrix[0].size(); j++) {
                dfs(matrix, i, j, 0, -1);  //find the max length starting from here
                memo[i][j] = res;  //store
                res = 0;
                ans = max( ans, memo[i][j]);
            }
        }

        return ans;
    }

    void dfs(vector< vector<int> >& matrix, int i, int j, int count, int pre) {
        if (i >= matrix.size() || i < 0 || j < 0 || j >= matrix[0].size() ||
                pre >= matrix[i][j]) {  //超出了界限 or not increased
                res = max(count, res);
            return;
        }

        if (memo[i][j] != 0) {  //use the value that got before
            res = max(res, count + memo[i][j]);
            return;
        }  //can reuse the value

        dfs(matrix, i - 1, j, count + 1, matrix[i][j]); //up
        dfs(matrix, i + 1, j, count + 1, matrix[i][j]); //down
        dfs(matrix, i, j + 1, count + 1, matrix[i][j]); //right
        dfs(matrix, i, j - 1, count + 1, matrix[i][j]); //left

        return;
    }
};