leetcode：329. Longest increasing path in matrix

Title source

• leetcode：329. The longest incremental path in the matrix

Title Description

class Solution {
    
public:
    int longestIncreasingPath(vector<vector<int>>& matrix) {
    

    }
};

title

Recurrence of violence

class Solution {
    
    int process(vector<vector<int>>& matrix, int i, int j){
    
    	// base case
        /*if(i < 0 || i == matrix.size() || j < 0 || j == matrix[0].size()){ return 0; } //  Because the boundary has been checked below , So here we can get rid of  */
        
        //  On 、 Next 、 Left 、 Right four attempts 
        int up =    i > 0                    && matrix[i - 1][j] > matrix[i][j] ? process(matrix, i - 1, j) : 0;
        int down =  i < matrix.size() - 1    && matrix[i + 1][j] > matrix[i][j] ? process(matrix, i + 1, j) : 0;
        int left =  j > 0                    && matrix[i][j - 1] > matrix[i][j] ? process(matrix, i, j - 1) : 0;
        int right = j < matrix[0].size() - 1 && matrix[i][j + 1] > matrix[i][j] ? process(matrix, i, j + 1) : 0;
        //  On 、 Next 、 Left 、 Choose the largest of the four choices on the right （ You can't go back ） +  own 
        return std::max(up, std::max(down, std::max(left, right))) + 1;
    }
public:
    int longestIncreasingPath(vector<vector<int>>& matrix) {
    
        int ans = 0;
        int m = matrix.size(), n = matrix[0].size();
        for (int i = 0; i < m; ++i) {
    
            for (int j = 0; j < n; ++j) {
      // Start from each position and try again 
                ans = std::max(ans, process(matrix, i, j));
            }
        }
        return ans;
    }
};

Will timeout

Memorandum

class Solution {
    
    int process(vector<vector<int>>& matrix, int i, int j, vector<vector<int>> &dp){
    
        if(dp[i][j] != 0){
      // If 0, It means that you have not calculated 
            return dp[i][j];  
        }
        
        int up =    i > 0                    && matrix[i - 1][j] > matrix[i][j] ? process(matrix, i - 1, j, dp) : 0;
        int down =  i < matrix.size() - 1    && matrix[i + 1][j] > matrix[i][j] ? process(matrix, i + 1, j, dp) : 0;
        int left =  j > 0                    && matrix[i][j - 1] > matrix[i][j] ? process(matrix, i, j - 1, dp) : 0;
        int right = j < matrix[0].size() - 1 && matrix[i][j + 1] > matrix[i][j] ? process(matrix, i, j + 1, dp) : 0;
        return dp[i][j] = std::max(up, std::max(down, std::max(left, right))) + 1;
    }
public:
    int longestIncreasingPath(vector<vector<int>>& matrix) {
    
        int ans = 0;
        int m = matrix.size(), n = matrix[0].size();
        vector<vector<int>> dp(m, std::vector<int>(n, 0));// dp[i][j] It can't be 0, Even if only I can be 1
        for (int i = 0; i < m; ++i) {
    
            for (int j = 0; j < n; ++j) {
    
                ans = std::max(ans, process(matrix, i, j, dp));
            }
        }
        return ans;
    }
};

Why is the memory search of this problem over

The dependent order of this question is chaotic , It's hard to tidy up , Rely only on Limited 4 A place , There is no need to optimize . Otherwise, it takes too much energy