329-矩阵中的最长递增路径

LeetCode 329. Longest Increasing Path in a Matrix

Given an m x n integers matrix, return the length of the longest increasing path in matrix.

From each cell, you can either move in four directions: left, right, up, or down. You may not move diagonally or move outside the boundary (i.e., wrap-around is not allowed).

Example 1:

Input: matrix = [[9,9,4],[6,6,8],[2,1,1]]
Output: 4
Explanation: The longest increasing path is [1, 2, 6, 9].

method: 记忆化搜索

单纯的每递归一次，num+1，然后取递归过程中num的最大值，会超时

写成有返回值的形式，返回从当前节点出发，能找到的最长递增路径的长度
这样就可以把每个节点的结果存储起来，后面再访问到直接返回

vector<vector<int>> hash;
const int next[4][2] = {{-1,0},{1,0},{0,-1},{0,1}}; // 上下左右
int dfs(vector<vector<int>>& matrix, int i, int j) {
    if (hash[i][j]) return hash[i][j];
    int num = 0;
    for (int k = 0; k < 4; k++) {
        int nx = i + next[k][0];
        int ny = j + next[k][1];
        if (nx >= 0 && nx < matrix.size() && 
            ny >= 0 && ny < matrix[0].size() && 
            matrix[nx][ny] > matrix[i][j]) {
            num = max(num, dfs(matrix, nx, ny));
        }
    }
    hash[i][j] = num + 1;
    return hash[i][j];
}
int longestIncreasingPath(vector<vector<int>>& matrix) {
    int res = 0;
    int m = matrix.size(), n = matrix[0].size();
    hash.resize(m, vector<int>(n));
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            res = max(res, dfs(matrix, i, j));
        }
    }
    return res;
}