【記憶化搜尋】329. 矩陣中的最長遞增路徑——了解記憶化搜尋的原理

【記憶化搜尋】329. 矩陣中的最長遞增路徑——思路分析

329. 矩陣中的最長遞增路徑

給定一個 m x n 整數矩陣 matrix ，找出其中 最長遞增路徑 的長度。

對于每個單元格，你可以往上，下，左，右四個方向移動。 你 不能 在 對角線 方向上移動或移動到 邊界外（即不允許環繞）。

輸入：matrix = [[9,9,4],[6,6,8],[2,1,1]]

輸出：4

解釋：最長遞增路徑為 [1, 2, 6, 9]。

這道題的正常解法是使用DFS算法，然而當該算法的時間複雜度為 O ( n 2 ) O(n^2) O(n2)，複雜度相當高了已經，當我上傳代碼時，果不其然……逾時了……

class Solution {
public:
    int directions[4][2] = {{0,1},{0,-1},{1,0},{-1,0}};
    vector<vector<int>> board;
    int dfs(int r,int c,int last_num,int len){
        // cout<<len<<endl;
        int maxlen = len;
        for(int i = 0;i<4;i++){
            int new_r = r + directions[i][0];
            int new_c = c + directions[i][1];
            if(new_c>=0 && new_r>=0 && new_r<board.size() && new_c<board[0].size() && board[new_r][new_c] > last_num){
                maxlen = max(dfs(new_r,new_c,board[new_r][new_c],len+1),maxlen);
            }
        }
        return maxlen;

    }
    int longestIncreasingPath(vector<vector<int>>& matrix) {
        board = matrix;
        vector<vector<int>> visited(matrix.size(),vector<int>(matrix[0].size(),0));
        int ans = 0;
        for(int i = 0;i<matrix.size();i++){
            for(int j = 0;j<matrix[i].size();j++){
                // cout<<dfs(visited,i,j,matrix[i][j],1)<<endl;
                ans = max(ans,dfs(i,j,matrix[i][j],1));
            }
        }
        return ans;
    }
};
           

那麼，也就要求我們必須進行優化，而優化的政策就是使用記憶化搜尋（我之前沒學過……據說這是記憶化搜尋模闆題……）

看了半天的題解，沒人說啥是記憶化搜尋，到底是怎麼運作的，終于讓我找到了一個說的明白的人，下面進入正題！！！

記憶化搜尋

在普通的DFS中，對于同一個位置如果我們通路多次的話，則需要計算多次，比如說從 1 − 2 − 4 − 7 − 9 1-2-4-7-9 1−2−4−7−9和從 3 − 5 − 7 − 9 3-5-7-9 3−5−7−9這兩條路徑中從7出發所對應的最長路徑需要計算兩次，顯然這是無效的，也是需要我們優化的地方。

如果我們設定一個二維數組，每次都記錄對應點所能經過的最長路徑長度，那麼如果被重複經過該點的話就可以直接調用值即可。

說道這如果還沒明白就看下面的這個例子：

如上圖所示，最長路徑應該是紅色連接配接的點，但是在進行DFS過程中，需要對每個起點進行周遊，假如從5又開始周遊了一次，起點5對應的最長路徑為藍色部分

我們可以發現，7、9、13又被計數了一次，通過觀察我們發現，從7出發的最長路徑隻有7-9-13，對應的長度應該是3，那麼等下次如果又有一個路線走到了7，我們可以直接傳回3啊，不用把後面的都跑一遍，這就是記憶化搜尋！！！！

在這道題目中，就是利用的這樣的一種思想，進而将時間複雜度從 O ( n 2 ) O(n^2) O(n2)降至 O ( m n ) O(mn) O(mn)，主要的做法是使用一個數組時刻記錄着每個點所對應的最長路徑長度，一旦走到該點則直接傳回結果值。

使用數學語言描述如下：

f [ i ] [ j ] f[i][j] f[i][j]表示從 ( i , j ) (i,j) (i,j)出發的最長路徑長度值

則：

f [ i ] [ j ] = m a x ( f [ x ] [ y ] ) , ( x , y ) 為 ( i , j ) 的 四 周 的 鄰 點 f[i][j]=max(f[x][y]),(x,y)為(i,j)的四周的鄰點 f[i][j]=max(f[x][y]),(x,y)為(i,j)的四周的鄰點

【代碼如下】

class Solution {
public:
    int directions[4][2] = {{0,1},{0,-1},{1,0},{-1,0}};
    vector<vector<int>> board;
    vector<vector<int>> store;
    int dfs(int r,int c){
        if(store[r][c]){
            return store[r][c];
        }
        int maxlen = 1;
        for(int i = 0;i<4;i++){
            int new_r = r + directions[i][0];
            int new_c = c + directions[i][1];
            if(new_c>=0 && new_r>=0 && new_r<board.size() && new_c<board[0].size() && board[new_r][new_c] > board[r][c]){
                maxlen = max(dfs(new_r,new_c)+1,maxlen);
            }
        }
        store[r][c] = maxlen;
        return maxlen;

    }
    int longestIncreasingPath(vector<vector<int>>& matrix) {
        board = matrix;
        vector<vector<int>> t(matrix.size(),vector<int>(matrix[0].size(),0));
        store = t;
        int ans = 0;
        for(int i = 0;i<matrix.size();i++){
            for(int j = 0;j<matrix[i].size();j++){
                ans = max(ans,dfs(i,j));
            }
        }
        return ans;
    }
};