2020-08-28 刷题1 矩阵中的最大值

329 矩阵中的最大值

普通深搜倒数第三个例子超时了，所以用了记忆数组来减少重复计算。设置pl数组，初始化全部为0，保存以（i，j）为路径开始，最长递增路径的长度。每次向四个方向搜索，如果某个方向的pl数组不为0，就直接拿过来加1，否则进入该方向搜索把其pl数组填上。最后遍历pl数组选择最大值。

class Solution {
public:
    int a[2][4] = {{0, 0, 1, -1}, {-1, 1, 0, 0}};
    int num_row, num_col;
    vector<vector<int>> pl;
    void dp(vector<vector<int>>& matrix, int i, int j){
        int max_path = 1;
        for(int k = 0; k < 4; k++){
            if(i + a[0][k] >= 0 && i + a[0][k] < num_row && j + a[1][k] >= 0 && j + a[1][k] < num_col){
                if(matrix[i + a[0][k]][j + a[1][k]] > matrix[i][j]){
                    if(pl[i + a[0][k]][j + a[1][k]] == 0)
                        dp(matrix, i + a[0][k], j + a[1][k]);
                    max_path = max(pl[i + a[0][k]][j + a[1][k]] + 1, max_path);
                }
            }
        }
        pl[i][j] = max_path;
    }
    int longestIncreasingPath(vector<vector<int>>& matrix) {
        if(matrix.size() == 0)
            return 0;
        int m_p = 0;
        num_row = matrix.size(), num_col = matrix[0].size();
        for(int i = 0; i < num_row; i++){
            vector<int> tmp(num_col, 0);
            pl.push_back(tmp);
        }
        for(int i = 0; i < num_row; i++){
            for(int j = 0; j < num_col; j++){
                if(pl[i][j] == 0)
                    dp(matrix, i, j);
            }
        }
        for(int i = 0; i < num_row; i++){
            for(int j = 0; j < num_col; j++)
                m_p = max(m_p, pl[i][j]);
        }
        return m_p;
    }
};