当前位置：首页 > article >正文

Leetcode—329. 矩阵中的最长递增路径【困难】

article 2024/9/24 13:24:41

2024每日刷题（165）

Leetcode—329. 矩阵中的最长递增路径

在这里插入图片描述

dfs + dp实现代码

class Solution {
public:
    int longestIncreasingPath(vector<vector<int>>& matrix) {
        // 9  9  4
        // 6  6  8
        // 2  1  1

        // 1  1  2
        // 2  2  1
        // 3  4  2

        int m = matrix.size();
        int n = matrix[0].size();
        vector<vector<int>> memo(m, vector<int>(n, 0));

        function<int(int, int, int)> dfs = [&](int i, int j, int pre) -> int {
            // out of boundary
            if(i < 0 || i == m || j < 0 || j == n) {
                return 0;
            }

            const int cur = matrix[i][j];
            if(cur <= pre) {
                return 0;
            }

            int &ans = memo[i][j];
            if(ans > 0) {
                return ans;
            }

            ans = 1 + max({
                dfs(i, j + 1, cur), dfs(i, j - 1, cur), dfs(i + 1, j, cur), dfs(i - 1, j, cur)
            });
            return ans;
        };
        
        int ans = 0;
        for(int i = 0; i < m; i++) {
            for(int j = 0; j < n; j++) {
                ans = max(ans, dfs(i, j, -1));
            }
        }
        return ans;
    }
};