LeetCode 329. 矩阵中的最长递增路径（dp）_给定一个m n整数矩阵matrix

题意：

给定一个 m x n 整数矩阵 matrix ，找出其中 最长递增路径 的长度。

对于每个单元格，你可以往上，下，左，右四个方向移动。 
你 不能 在 对角线 方向上移动或移动到 边界外（即不允许环绕）。

数据范围:
m == matrix.length
n == matrix[i].length
1 <= m, n <= 200
0 <= matrix[i][j] <= 2^31 - 1
1
2
3
4
5
6
7
8
9
10

解法：

因为只能从小的点走到大的点,所以是DAG,可以dp.

令d[i][j]表示从a[i][j]出发能走的最大路径,可以向四个方向转移.
1
2
3

code：

int dx[]={0,0,1,-1};
int dy[]={1,-1,0,0};
class Solution {
public:
    int d[222][222];
    int n,m;
    int dfs(vector<vector<int> >&a,int i,int j){
        if(~d[i][j])return d[i][j];
        d[i][j]=1;
        for(int k=0;k<4;k++){
            int xx=i+dx[k];
            int yy=j+dy[k];
            if(xx<0||xx>=n||yy<0||yy>=m)continue;
            if(a[i][j]<a[xx][yy]){
                d[i][j]=max(d[i][j],dfs(a,xx,yy)+1);
            }
        }
        return d[i][j];
    }
    int longestIncreasingPath(vector<vector<int>>& a) {
        memset(d,-1,sizeof d);
        n=a.size(),m=a[0].size();
        int ans=0;
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                ans=max(ans,dfs(a,i,j));
            }
        }
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31