【LeetCode】329. 行列内の最長インクリメントパス結題レポート(C++)

原題住所:https://leetcode-cn.com/problems/longest-increasing-path-in-a-matrix/submissions/
タイトルの説明:
整数行列を指定し、最長のインクリメントパスの長さを見つけます.
各セルについて、上、下、左、右の4つの方向に移動できます.対角線方向に移動したり、境界外に移動したりすることはできません(つまり、周囲を許可しません).
例1:
入力:nums=[[9,9,4],[6,6,8],[2,1,1]]出力:4解釈:最長増分経路は[1,2,6,9].例2:
入力:nums=[[3,4,5],[3,2,6],[2,2,1]]出力:4解釈:最長インクリメントパスは[3,4,5,6]である.注意対角線方向の移動は許可されていません.
 
問題解決方案:
まず,深さ優先遍歴アルゴリズムを考え,この方法は2次元配列を用いて4つの方向を定義した.深度は優先的にループし、ノードからずっとループします.ここのコードはまだ最適化されておらず,時間的複雑さが大きい.
コード:

class Solution {
public:
    vector> state = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
    
    int longestIncreasingPath(vector>& matrix) {
        int n = matrix.size();
        if (n == 0) 
            return 0;
        int m = matrix[0].size();

        vector> dp(n, vector(m, 0));
        int res = 0;
        for (int i = 0; i < n; i++)
            for (int j = 0; j < m; j++) 
                res = max(dfs(dp, matrix, i, j), res);
        return res;
    }
    
    int dfs(vector>& dp, vector> matrix, int i, int j) {
        if (dp[i][j] != 0) 
            return dp[i][j];
        dp[i][j] = 1;
        for (vector s : state) {
            int x = i + s[0];
            int y = j + s[1];
            if (x >= 0 && x < matrix.size() && y >= 0 && y < matrix[0].size() && matrix[i][j] < matrix[x][y])
                dp[i][j] = max(dp[i][j], dfs(dp, matrix, x, y) + 1) ;
        }
        return dp[i][j];
    }
};

時間の複雑さが最小の答え:

class Solution {
public:
    int m, n; 
    vector> memo;
    int dfs(vector>& matrix, int x, int y) {
        if(memo[x][y] != -1)
            return memo[x][y];
        int ret = 1;        
        if(x>0 && matrix[x-1][y]>matrix[x][y]) 
            ret = max(ret, 1 + dfs(matrix, x-1, y));
        if(xmatrix[x][y])
            ret = max(ret, 1 + dfs(matrix, x+1, y));
        if(y>0 && matrix[x][y-1]>matrix[x][y])
            ret = max(ret, 1 + dfs(matrix, x, y-1));
        if(ymatrix[x][y])
            ret = max(ret, 1 + dfs(matrix, x, y+1));
        memo[x][y] = ret;
        return ret;
    }
    int longestIncreasingPath(vector>& matrix) {
        m = matrix.size();
        if(m == 0) return 0;
        n = matrix[0].size();
        memo.resize(m);
        int ans = 1;
        for(int i = 0; i < m; ++i) memo[i].resize(n, -1);
        for(int i = 0; i < m; ++i) {
            for(int j = 0; j < n; ++j) {
                int temp = dfs(matrix, i, j);
                ans = ans < temp ? temp : ans;
            }
        }
        return ans;
    }
};