LeetCode 329 Longest Increasing Path in a Matrix

    
        标签：
        
            动态规划问题
        
            LeetCode
        
    发布于：2022-03-07 16:32:58
    编辑于：2022-03-07 16:50:21
    浏览量：703

概述

https://leetcode.com/problems/longest-increasing-path-in-a-matrix/

动态规划法

不懂，为啥这道题被标记为 Hard。。。

注意不能对角线移动！

class Solution {
public:
    vector<vector<int>> dp;
    int longestIncreasingPath(vector<vector<int>>& matrix) {
        dp.resize(matrix.size(), vector<int>(matrix[0].size(), -1));
        int ans = 0;
        for (int i = 0; i < matrix.size(); i ++) {
            for (int j = 0; j < matrix[0].size(); j ++) {
                ans = max(ans, helper(matrix, i, j));
                // cout << i << " " << j <<" " << dp[i][j] << endl;
            }
        }
        return ans;
    }
    
    int helper(vector<vector<int>>& matrix, int i, int j) {
        if (dp[i][j] != -1) return dp[i][j];
        int rest = 0;
        for (int m = max(0, i-1); m < min(int(matrix.size()), i+2); m ++) {
            if (m == i) continue;
            if (matrix[i][j] < matrix[m][j]) rest = max(rest, helper(matrix, m, j));
        }
        for (int n = max(0, j-1); n < min(int(matrix[0].size()), j+2); n ++) {
            if (n == j) continue;
            if (matrix[i][j] < matrix[i][n]) rest = max(rest, helper(matrix, i, n));
        }        
        dp[i][j] = 1 + rest;
        return dp[i][j];
    }
};

Links: leetcode-329-longest-increasing-path-in-a-matrix