LEETCODE ALGORITHM:329. Longest Increasing Path in a Matrix

发表于 更新于 分类于 Waline： 阅读次数：

题目

Given an integer matrix, find the length of the longest increasing path.

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

Example 1:

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

Example 2:

1
2
3
4
5
6
7
8
Input: nums = 
[
  [3,4,5],
  [3,2,6],
  [2,2,1]
] 
Output: 4 
Explanation: The longest increasing path is [3, 4, 5, 6]. Moving diagonally is not allowed.

题解

dfs

从所有点出发进行dfs，找最长路径，必须要保存中间结果，否则一定会超时

没用vis是因为一直在找更大的数，不会重复走

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
32
33
34
class Solution {
private:
    int dir[4][2]={{0,1},{0,-1},{1,0},{-1,0}};
    vector<vector<int>> cache;
    int dfs(vector<vector<int>>&matrix,int x,int y)
    {
        if(cache[x][y]!=0) return cache[x][y];
        for(int i=0;i<4;i++)
        {
            int t1=x+dir[i][0];
            int t2=y+dir[i][1];
            if(t1>=0&&t1<matrix.size()&&t2>=0&&t2<matrix[0].size()&&matrix[t1][t2]>matrix[x][y])
            {
                cache[x][y]=max(dfs(matrix,t1,t2)+1,cache[x][y]);
            }
        }
        if(cache[x][y]==0) cache[x][y]=1;
        return cache[x][y];
    }
public:
    int longestIncreasingPath(vector<vector<int>>& matrix) {
        if(matrix.size()==0) return 0;
        cache.assign(matrix.size(),vector<int>(matrix[0].size(),0));
        int ans=0;
        for(int i=0;i<matrix.size();i++)
        {
            for(int j=0;j<matrix[0].size();j++)
            {
                ans=max(ans,dfs(matrix,i,j));
            }
        }
        return ans;
    }
};

dp