LeetCode - 329. Longest Increasing Path in a Matrix

Category: Algorithm
Difficulty: Hard
Tags: Depth-first Search, Topological Sort, Memoization
Discription: https://leetcode.com/problems/longest-increasing-path-in-a-matrix/#/description

雖然難度定義是難題，但此題應該是難題中較為友善的題目了。
題目會給一個整數的二維陣列，讓我們去找出由遞增數字所連成的最長路徑，並回傳長度。

Example 1:

nums = [
  [9,9,4],
  [6,6,8],
  [2,1,1]
]

Return 4

The longest increasing path is [1, 2, 6, 9].

Example 2:

nums = [
  [3,4,5],
  [3,2,6],
  [2,2,1]
]

Return 4
The longest increasing path is [3, 4, 5, 6]. Moving diagonally is not allowed.

首先，這題一定要實踐DFS，並可由各個元素開始走訪。(這裡是以遞迴實踐，但以Stack實踐應該也是可行的)
接下來，為了最佳化搜尋，我們另外建立一個相同大小的二維陣列(dp)紀錄走訪成果，以實作DP。
class Solution {
public:
    int longestIncreasingPath(vector<vector<int>>& matrix) {
        if(matrix.empty()) return 0;
     
        int result = 1;
        int m = matrix.size();
        int n = matrix[0].size();
        vector<vector<int>> dp(m, vector<int>(n, 0));
        // m*n dynamic matrix, initial value is 0
     
        for(int i=0; i<m; i++)
            for(int j=0; j<n; j++)
                result = max(result, dfs(matrix, i, j, dp));
     
        return result;
    }
 
    int dfs(vector<vector<int>>& matrix, int i, int j, vector<vector<int>>& dp) {
    // using reference to transport matrix contributes to MLS
        if(dp[i][j] != 0) return dp[i][j];
     
        int dir[4][2] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
        int dist = 1;
        int m = matrix.size();
        int n = matrix[0].size();
     
        for(int dir_i=0; dir_i<4; dir_i++) {
            int next_i=i+dir[dir_i][0], next_j=j+dir[dir_i][1];
            if(next_i<0 || next_j<0 || next_i>=m || next_j>=n || matrix[next_i][next_j]>=matrix[i][j]) continue;
            // This contributes to TLS
            dist = max(dist, dfs(matrix, next_i, next_j, dp)+1);
        }
     
        dp[i][j] = dist;
        return dist;
     
    }
};
決定好使用的演算法後，

這裡實踐上比較重要的便是function dfs(......)內的分支判斷式(if)，
if(next_i<0 || next_j<0 || next_i>=m || next_j>=n || matrix[next_i][next_j]>=matrix[i][j]) continue;
// This contributes to TLS
dist = max(dist, dfs(matrix, next_i, next_j, dp)+1); 這個判斷式的目的是篩選掉超出陣列範圍的索引，以及比對出遞增數字以進行DFS走訪，
處理的不好便很有可能會得到TLE(Time Limit Exceeded)的結果。
反向思考使用AND來處理，也是可行的：
if(next_i>=0 && next_j>=0 && next_i<m && next_j<n && matrix[next_i][next_j]<matrix[i][j])
    dist = max(dist, dfs(matrix, next_i, next_j, dp)+1);
另一個重點，在呼叫function dfs(......)時，必須使用傳址或傳參呼叫，
因為本題有記憶體空間的限制，如果使用傳值呼叫，在最後一個測資(Test Case)便會因為MLE(Memory Limit Exceeded)而無法通過。

現在來細說我們的DFS走訪，
首先，我們有兩個相同大小的陣列matrix & dp(初始值為0)，
而陣列dp是用來記錄「行走距離」的，
走訪matrix的每一個元素時都先檢查dp所紀錄相對應索引的值是否不為0，
如果不為0就代表這個元素已經走訪過了，也被賦予了「行走距離」，如此便可以直接return此「行走距離」。
但如果為0呢？那我們就要繼續走訪下去了(使用遞迴)，直到無法走訪為止！
因此，遞迴終止時，便會由最後的元素依序回傳「行走距離」1, 2, 3, 4, ......直到返回我們的進入元素為止。
當然，「行走距離」會被記錄在dp上，以便下一次的走訪使用。
如果由另一個進入元素走訪時，遇到dp已經被賦予了「行走距離」的元素呢？
在這裡可以使用max函式來選擇較大的「行走距離」，便可以輕鬆解決這個問題。