leetcode 329. Longest Increasing Path in a Matrix 矩阵中寻找最长递增序列 + 一个典型的深度优先遍历DFS的做法

不念不忘少年蓝@ 2022-06-07 01:10 158阅读 0赞

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:

nums = \[  
\[9,9,4\],  
\[6,6,8\],  
\[2,1,1\]  
\]  
Return 4  
The longest increasing path is \[1, 2, 6, 9\].

Example 2:

nums = \[  
\[3,4,5\],  
\[3,2,6\],  
\[2,2,1\]  
\]  
Return 4  
The longest increasing path is \[3, 4, 5, 6\]. Moving diagonally is not allowed.

这道题很简单，直接DFS遍历即可，不过这里使用了一个dp数组来做剪纸处理，属于一个很基本的DFS深度有限遍历的应用。

**需要注意的地方是，我们我们把一个前一个元素的值作为比较的值，这里的递增是严格递增，**

DFS的做法很不错，和这一道题[leetcode 375. Guess Number Higher or Lower II 按照length动态规划DP + 最大最小化问题][leetcode 375. Guess Number Higher or Lower II _length_DP _]的做法很相似，建议一起学习

代码如下：

/*
     * 没什么就是一个简单的最基本的DFS深度优先遍历的应用
     * */
    class Solution
    {
        public int longestIncreasingPath(int[][] matrix) 
        {
            if(matrix.length<=0 || matrix[0].length <=0) 
                return 0;
            int max=0, n = matrix.length, m = matrix[0].length;
            int [][] dp = new int[n][m];
            for(int i=0;i<matrix.length;i++)
            {
                for(int j=0;j<matrix[0].length;j++)
                {
                    max = Math.max(max, maxLen(matrix, Integer.MIN_VALUE, i, j, dp));
                }
            }
            return max;
        }
    
        public int maxLen(int[][] matrix, int pre, int i, int j, int[][] dp)
        {
            if(i<0 || j<0 || i>=matrix.length || j>= matrix[0].length || matrix[i][j] <= pre) 
                return 0;
            else if(dp[i][j] != 0) 
                return dp[i][j];
            else 
            {
                pre = matrix[i][j];
                int up = maxLen(matrix, pre, i-1, j, dp) + 1;
                int left = maxLen(matrix, pre, i, j-1, dp) + 1;
                int right = maxLen(matrix, pre, i, j+1, dp) + 1;
                int down = maxLen(matrix, pre, i+1, j, dp) + 1;
                dp[i][j] = Math.max(up, Math.max(left, Math.max(right,down)));     
                return dp[i][j];
            }
        }
    }

下面是C++的做法，

代码如下：

#include <iostream>
    #include <vector>
    #include <map>
    #include <unordered_map>
    #include <set>
    #include <unordered_set>
    #include <queue>
    #include <stack>
    #include <string>
    #include <climits>
    #include <algorithm>
    #include <sstream>
    #include <functional>
    #include <bitset>
    #include <numeric>
    #include <cmath>
    #include <regex>
    
    using namespace std;
    
    
    
    class Solution 
    {
    public:
        int longestIncreasingPath(vector<vector<int>>& mat)
        {
            if (mat.size() <= 0)
                return 0;
    
            int row = mat.size() , col = mat[0].size();
            vector<vector<int>> dp(row, vector<int>(col, 0));
            int res = 0;
            for (int i = 0; i < row; i++)
            {
                for (int j = 0; j < col; j++)
                {
                    int one = dfs(mat, dp, INT_MIN, i, j);
                    res = max(res, one);
                }
            }
            return res;
        }
    
        int dfs(vector<vector<int>>& mat, vector<vector<int>>& dp, int pre, int x, int y)
        {
            int row = mat.size(), col = mat[0].size();
            if (x < 0 || x >= row || y<0 || y >= col || pre >= mat[x][y])
                return 0;
            else if (dp[x][y] != 0)
                return dp[x][y];
            else
            {
                pre = mat[x][y];
                int left =  dfs(mat, dp, pre, x - 1, y) + 1;
                int right = dfs(mat, dp, pre, x + 1, y) + 1;
                int up =    dfs(mat, dp, pre, x, y + 1) + 1;
                int down =  dfs(mat, dp, pre, x, y - 1) + 1;
                dp[x][y] = max(left, max(right, max(up, down)));
                return dp[x][y];
            }
        }
    };

[leetcode 375. Guess Number Higher or Lower II _length_DP _]: http://blog.csdn.net/jackzhang_123/article/details/78173532