leetcode：329. 矩阵中的最长递增路径

题目来源

• leetcode：329. 矩阵中的最长递增路径

题目描述

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

    }
};

题目解析

暴力递归

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; } // 因为下面已经检查了边界，所以这里可以去掉 */
        
        // 上、下、左、右四种尝试
        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;
        // 上、下、左、右四种选择中选一种最大的（不能走回头路） + 自己
        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) {
      //每个位置出发试一遍
                ans = std::max(ans, process(matrix, i, j));
            }
        }
        return ans;
    }
};

会超时

备忘录

class Solution {
    
    int process(vector<vector<int>>& matrix, int i, int j, vector<vector<int>> &dp){
    
        if(dp[i][j] != 0){
      //如果为0，表示没有算过
            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]不可能为0，哪怕只有自己也会是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;
    }
};

为什么这道题记忆化搜索就结束了

本题依赖顺序是乱的，不好整理，只依赖有限的4个位置，没有必要再优化了。否则太花精力了