題目網址：https://leetcode.cn/problems/longest-increasing-path-in-a-matrix/

題意：給一 m x n 整數矩陣 matrix, 找出其中最長遞增路徑的長度。

對於每個 cell, 可以往上、下、左、右四個方向移動。

不能在對角線方向上移動 or 移動到邊界外。

Solution：

想法：利用 DFS + DP, 其中 dp[i][j] 紀錄以 (i, j) 為起點的最長遞增路徑之長度。透過 DP 可避免重複計算。e.g. 假設先計算完 dfs(A), 只後執行 dfs(C) 時, 發現 C 會拜訪 A, 透過 DP 可直接得到先前計算過的 dfs(A), 而不用重新計算

class Solution {
public:
    int longestIncreasingPath(vector<vector<int>>& matrix) {
        m = matrix.size(), n = matrix[0].size();
        dp.resize(m, vector<int>(n, 0));

        int res = 0;
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                res = max(res, dfs(matrix, i, j));
            }
        }

        return res;
    }

private:
    int m, n;
    vector<vector<int>> dp;
    vector<pair<int, int>> dirs = {
        {1, 0}, {-1, 0},
        {0, 1}, {0, -1}
    };

    bool outOfBound(const int i, const int j){
        if (i < 0 || i >= m || j < 0 || j >= n) {
            return true;
        }
        return false;
    }

    int dfs(vector<vector<int>>& matrix, int i, int j){
        if (dp[i][j] != 0) { // 如果已計算過 (i, j), 則直接返回
            return dp[i][j];
        }

        int res = 1; // 每個 cell 的最小長度為 1 (path 中只有自己)

        for (const auto& dir : dirs) {
            const int newY = i + dir.first;
            const int newX = j + dir.second;

            if (outOfBound(newY, newX)) { // 若超出邊界, 則跳過
                continue;
            }

            if (matrix[newY][newX] <= matrix[i][j]) { // 若非遞增, 則跳過
                continue;
            }

            res = max(res, 1 + dfs(matrix, newY, newX));
        }

        dp[i][j] = res; // 用 dp[i][j] 紀錄以 (i, j) 為起點的最長遞增路徑之長度

        return res;
    }
};
  • time：$O(m \cdot n)$ ➔ 每個 matrix[i][j] 最多拜訪一次
  • space：$O(m \cdot n)$ ➔ dp