LeetCode/solutions/329. Longest Increasing Path in a Matrix.md

# [329. Longest Increasing Path in a Matrix](https://leetcode.com/problems/longest-increasing-path-in-a-matrix/)

# 思路

给定一个二维矩阵，求矩阵中最长的递增路径。我们可以从尝试从每个位置出发进行DFS，计算出以每个位置为起始的最长递增路径，最后返回最长即可。注意到DFS会存在大量重复，所以我们需要开辟一个二维记忆数组`cache`，`cache[i][j]`表示以位置ij为起始的最长递增路径长度，初始为0。当我们进行DFS时，如果发现`cache[i][j] > 0`，说明之前已经计算过了，无需再进行计算，直接返回`cache[i][j]`即可。

# C++
``` C++
class Solution {
private:
    int m, n;
    vector<vector<int>>cache;
    int DFS(const vector<vector<int>>& matrix, int i, int j){
        if(cache[i][j] > 0) return cache[i][j];
        
        int sub_res = 0;
        if(i > 0 && matrix[i-1][j] > matrix[i][j]) sub_res = max(sub_res, DFS(matrix, i-1, j));
        if(j > 0 && matrix[i][j-1] > matrix[i][j]) sub_res = max(sub_res, DFS(matrix, i, j-1));
        if(i < m-1 && matrix[i+1][j] > matrix[i][j]) sub_res = max(sub_res, DFS(matrix, i+1, j));
        if(j < n-1 && matrix[i][j+1] > matrix[i][j]) sub_res = max(sub_res, DFS(matrix, i, j+1));
        
        cache[i][j] = 1 + sub_res;
        return cache[i][j];
    }
public:
    int longestIncreasingPath(vector<vector<int>>& matrix) {
        m = matrix.size();
        if(!m) return 0;
        n = matrix[0].size();
        
        cache = vector<vector<int>>(m, vector<int>(n, 0));
        int res = 0;
        for(int i = 0; i < m; i++)
            for(int j = 0; j < n; j++)
                res = max(res, DFS(matrix, i, j));

        return res;
    }
};
```