本篇文章要來探討 Leetcode #329 Longest Increasing Path in a Matrix 。

方法 1 DFS + Memorization

單純的做 DFS 也可以找出最長 path ，但是時間複雜度太大。

觀察每次的 DFS ，會發現有許多重複子問題，以下圖的 matrix[0][1] 為例 ，他可能由左手邊跟下方的點走到 (0,1) 位置，代表從這個點出發作 DFS 會發生兩次，

想避免做重複子問題，如同動態規劃做法，將曾經做過的結果 cache 起來，避免重複計算，因此這題採取 DFS 加上 cache 來解決。

有一點值得一提，通常不會用 DFS 搭配 cache 作法，因為你很可能會走到重覆的路徑而導致形成 cycle ，但因為這題有了 increasing order 的限制，因而避開形成 cycle 的可能性。

class Solution {
public:
    int dir_row[4] = {-1, 0, 1, 0};
    int dir_col[4] = {0, -1, 0, 1};

    int longestIncreasingPath(vector<vector<int>>& matrix) {
        int max_len = 1;
        vector<vector<int>> cache (matrix.size(), vector<int>(matrix[0].size(), 0));
        for (int i=0; i<matrix.size(); i++) {
            for (int j=0; j<matrix[0].size(); j++) {
                max_len = std::max(max_len, dfs_helper(matrix, cache, i, j));
            }
        }
        return max_len;
    }

    int dfs_helper (vector<vector<int>>& matrix, vector<vector<int>>& result,
                    int row, int col) {
        if (result[row][col] != 0) {
            return result[row][col];
        }
        for (int i=0; i<4; i++) {

            int next_row = row + dir_row[i];
            int next_col = col + dir_col[i];

            if (next_row >=0 && next_row < matrix.size()
               && next_col >= 0 && next_col < matrix[0].size()
               && matrix[next_row][next_col] > matrix[row][col]) 
            {
                result[row][col] = 
                    std::max (dfs_helper(matrix, result, next_row, next_col)+1, result[row][col]);
            }
        }
        if (result[row][col] == 0) result[row][col] = 1;
        return result[row][col];
    }
};

Time Complexity O(mn)
Space Complextiy O(mn)

方法 2 Topological sort

根據題目的要求，將 Increasing path 連結起來，就可以將 matrix 看成是一個 DAG (有向連通圖) ，畫成圖後，對於要找出最長的 path 就更加容易理解了。

在一個 DAG 中，想要梳理出這樣的前後關係，可以想到 Topological sort ，在 topological sort 過程中，每輪都會選擇 inDgree 為 0 的點，做為新一輪的延伸，因此我們可以說總共做了幾輪，也就代表找到最長 path 的長度。 你可以透過上圖幫助你理解，並且搭配本站之前的文章 Topological Sort – 陪你刷題來複習 topological sort 。

class Solution {
public:
    int dir_row[4] = {-1, 0, 1, 0};
    int dir_col[4] = {0, 1, 0, -1};
    int longestIncreasingPath(vector<vector<int>>& matrix) {
        int row = matrix.size();
        int col = matrix[0].size();
        vector<vector<int>> indegree(row, vector<int>(col, 0));

        for(int i=0; i<row; i++) {
            for (int j=0; j<col; j++) {
                for (int k=0; k<4; k++) {
                    int neighbor_row = i+dir_row[k];
                    int neighbor_col = j+dir_col[k];
                    if (neighbor_row >= 0 && neighbor_row < row
                       && neighbor_col >=0 && neighbor_col <col
                       && matrix[neighbor_row][neighbor_col] < matrix[i][j]){
                        indegree[i][j]++;
                    }
                }

            }
        }

        queue<pair<int, int>> qu;
        for (int i=0; i<row; i++) {
            for (int j=0; j<col; j++) {
                if (indegree[i][j] == 0) {
                    qu.push({i,j});
                }
            }
        }

        int len = 0;
        while (!qu.empty()) {
            len++;
            int size = qu.size();
            for (int i=0; i<size; i++) {
                pair<int, int> node = qu.front();
                qu.pop();
                // Check all its neighbor node
                for (int d=0; d<4; d++) {
                    int neighbor_row = node.first + dir_row[d];
                    int neighbor_col = node.second + dir_col[d];

                    if (neighbor_row >= 0 && neighbor_row < row
                       && neighbor_col >=0 && neighbor_col <col
                       && matrix[neighbor_row][neighbor_col] 
                        > matrix[node.first][node.second]){
                        indegree[neighbor_row][neighbor_col]--;
                        if (indegree[neighbor_row][neighbor_col] == 0) {
                            qu.push({neighbor_row, neighbor_col});
                        }
                    }
                }
            }
        }
        return len;
    }
};

Time Complexity O(mn)

Space Complexity O(mn)