查找最長遞增路徑矩陣

Question

這就是網上法官， https://leetcode.com/problems/longest-increasing-path-in-a-matrix/

爲什麼我不能使用DFS的結果呢？

正如您從每個單元格中所示，請移動到四個方向：左，右，向上或向下。

存儲最長增加路徑的長度。

/* 

for each elem, neighbours dfs 

*/ 
class Solution { 
public: 
    int longestIncreasingPath(vector<vector<int>>& matrix) { 
     int row = matrix.size(); 
     int col = matrix[0].size(); 
     int x[] = {0,1,0,-1};// l-r  -1,1  
     int y[] = {1,0,-1,0};// up-down +1,-1 
     int maxlen = 0; 

     for(int i = 0; i < row; i++){ 
      for(int j = 0; j< col; j++){ 
       // each node in the matrix[i][j], neighbours 
       int len = 0; 
       dfs(maxlen, len, i, j, x, y, matrix); 
      } 
     } 
     return maxlen; 
    } 

private: 
    bool isIn(int x, int y, int row, int col){ 
     if(x>=0&&x<=col && y>=0&&y<=row) return true; 
     else return false; 
    } 

    void dfs(int& maxlen, int len, int i, int j,int* x, int* y, vector<vector<int>> matrix){ 
     int row = matrix.size(); 
     int col = matrix[0].size(); 

     for(int k = 0; k < 4; k++){ 
      int i_t = i+x[k];//the current position 
      int j_t = j+y[k]; 
      if(isIn(i_t,j_t,row,col)&& (matrix[i_t][j_t]>matrix[i][j])){ // if inside the matrix, within the boundary&& the value of (i_t,j_t)> 
       len+=1; 
       maxlen = max(len,maxlen); 
       dfs(maxlen, len, i_t, j_t, x, y, matrix); 
      } 
     } 
    } 
}; 

Answer 1

該代碼有多個問題。

1. if(x>=0&&x<=col && y>=0&&y<=row)應改爲if(x>=0&&x<col && y>=0&&y<row)

2. 您將所有從一個元素在一起會產生一個錯誤的答案來源的路徑。 的代碼

   len+=1; 
   maxlen = max(len,maxlen); 
   dfs(maxlen, len, i_t, j_t, x, y, matrix); 
   

   這部分應改爲：

   //len+=1; 
   maxlen = max(len+1,maxlen); 
   dfs(maxlen, len+1, i_t, j_t, x, y, matrix); 
   

   ，這樣你就不會在不同的方向上添加所有的路徑在一起。

   1. 您正在解決大量重疊問題。一旦您撥打dfs(r,c)，您可以保存其結果，並將該值用於將來的參考（動態編程）。

這是我怎麼會實現它：

#include <vector> 
#include <iostream> 
#include <map> 
using namespace std; 

map< pair<int,int>, int > dp; 
pair<int,int> moves[] = {{0,1},{0,-1},{1,0},{-1,0}}; 
vector<vector<int> > matrix = { {3,4,5}, 
           {3,2,6}, 
           {2,2,1}}; 

int dfs(int r, int c, int n_rows, int n_cols){ 
    pair<int,int> p = make_pair(r,c); 
    if (dp.count(p)){ 
     return dp[p]; 
    } 
    int mx = 0; 
    for (int i=0; i<4; ++i){ 
     int next_r = r+moves[i].first; 
     int next_c = c+moves[i].second; 
     if (0<=next_r && next_r < n_rows && 0<=next_c && next_c < n_cols){ 
      if (matrix[next_r][next_c] > matrix[r][c]) 
       mx = max(mx, dfs(next_r, next_c, n_rows, n_cols)); 
     } 
    } 
    mx++; 
    dp[p] = mx; 
    return mx; 
} 

int main(){ 
    int rows = matrix.size(); 
    int cols = matrix[0].size(); 
    int result = 0; 
    for (int i=0; i<rows; ++i){ 
     for (int j=0; j<cols; ++j){ 
      result = max(result, dfs(i,j,rows,cols)); 
     } 
    } 
    cout << result << endl;          
}