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

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

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 + 最大最小化问题的做法很相似，建议一起学习

代码如下：

/*
 * 没什么就是一个简单的最基本的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];
        }
    }
};