矩阵中的最长递增路径【深度优先搜索】【动态规划 广度优先搜索】

给定一个整数矩阵，找出最长递增路径的长度。 对于每个单元格，你可以往上，下，左，右四个方向移动。 你不能在对角线方向上移动或移动到边界外（即不允许环绕）。

示例 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]。注意不允许在对角线方向上移动。

方法1：记忆化的深度优先搜索
将矩阵看成一个有向图，每个单元格对应图中的一个节点，如果相邻的两个单元格值不相等，则在相邻两个单元格 之间存在一条从较小指向较大值的有向边。那么问题转化为在有向图中寻找最长路径。
深度优先搜索是非常直观的方法。从一个单元格开始进行深度优先搜索，就可以找到该单元格开始的最长递增路径。对每一个单元格分别进行深度优先搜索以后，就可以得到矩阵中最长的递增路径。

空间换时间：如果使用朴素的优先搜索，时间复杂度是指数级的。朴素的深度优先搜索时间复杂度过高是因为进行了大量的重复计算。 同一个单元格会被访问多次。每一次访问都需要重复计算。同一个单元格对应的最长递增路径长度是固定不变的，因此可以使用记忆化的方法 进行优化。采用举证memo作为缓存矩阵，将已经计算过的结果存储在缓存矩阵中。<br />    使用方法：在使用记忆化的深度优先搜索，当访问一个单元格(i, j)时候，如果memo[i][j] != 0，说明该单元格的结果已经计算过；<br />    则直接从缓存中读取结果，如果memo[i][j] = 0，该单元格结果还没有被计算过，则进行搜索，并将计算结果存入缓存。

int dy_dx[4][2] = {{1, 0}, {-1, 0}, {0, -1}, {0, 1}}; // 上下左右偏移量
int m;
int n;

int dfs(vector<vector<int>> &matrix, int y, int x, vector<vector<int>> &memo){
    if(memo[y][x] != 0)     // 该单元格的最长递增路径已经算过了
        return memo[y][x];

    ++memo[y][x];           // 单元格自身长度为1

    // 上下左右(深度优先)搜索单元格(row, col)的递增路劲
    for(int i=0; i<4; ++i){
        int new_y = y + dy_dx[i][0];
        int new_x = x + dy_dx[i][1];
        if (new_y >= 0 && new_y < m && new_x >= 0 && new_x < n && matrix[y][x] < matrix[new_y][new_x]){
            memo[y][x] = max(memo[y][x], dfs(matrix, new_y, new_x, memo) + 1);  // dfs(*) + 1
        }
    }
    return memo[y][x];
}

int longestIncreasingPath(vector<vector<int>>& matrix) {
    if (matrix.size() == 0 || matrix[0].size() == 0)
        return 0;

    m = matrix.size();
    n = matrix[0].size();
    auto memo = vector<vector<int>>(m, vector<int>(n, 0));
    int ans = 0;
    for(int i=0; i<m; ++i){
        for(int j=0; j<n; ++j){
            ans = max(ans, dfs(matrix, i, j, memo));    // 开始深度优先搜索求(i, j)单元格的最长递增序列长度
        }
    }
    return ans;
}
// 时间复杂度：O(mn), 深度优先搜索的时间复杂度O(V+E),V为节点数，E为边数。O(V)=O(mn), O(E)~=O(4mn)
// 空间复杂度： O(mn); 缓存和递归调用深度;

========================================================================
// 方法2： 动态规划

由于每一个单元格对应增长路径的结果只与相邻的单元格有关，可以使用动态规划来解决此问题；<br />    设memo[i][j]表示单元格[i,j]的状态值(最长递增长度)，状态转移如下：<br />            memo[i][j] = max(memo[x][y]) + 1;  其中[x,y]与[i,j]相邻，而且matrix[x][y] > matrix[i][j]<br />    边界：<br />    1、单元格的值比所有相邻单元格值大，单元格对应的最长递增路径为1.<br />    2、将矩阵看成有向图，计算每一个单元格对应的【出度】, 多少条边从该单元格出发，对应于边界条件的单元格，该单元格<br />    的值比所有相邻单元格值都大。因此作为边界的单元格的出度都是0.

拓扑排序：从出度为0的单元格开始广度优先搜索，每一轮都会遍历当前层的所有单元格，<br />        更新其余单元格的出度，并将出度变为0的单元格加入下一层，当搜索结束时候,搜索总层数就为矩阵中的最长递增路径长度；

int dy_dx[4][2] = {{1, 0}, {-1, 0}, {0, -1}, {0, 1}}; // 上下左右偏移量
int m;
int n;

int longestIncreasingPath(vector<vector<int>> & matrix){
    if (matrix.size() == 0 || matrix[0].size() == 0)
        return 0;
    m = matrix.size();
    n = matrix[0].size();
    auto out_degrees = vector<vector<int>> (m, vector<int>(n, 0));
    // calc out_degree
    for(int y=0; y<m; ++y){
        for(int x=0; x<n; ++x){
            for(int i=0; i<4; ++i){
                int new_y = y + dy_dx[i][0];
                int new_x = x + dy_dx[i][1];
                if (new_y >= 0 && new_y < m && 
                    new_x >= 0 && new_x < n &&
                    matrix[new_y][new_x] < matrix[y][x])
                    ++out_degrees[y][x];
            }
        }
    }

    // 广度优先搜索(用到队列)：出度为0的单元格(i, j)入队列
    queue<pair<int, int>> Q;
    for(int y=0; y<m; ++y){
        for(int x=0; x<n; ++x){
            if(out_degrees[y][x] == 0)
                Q.push({y, x});
        }
    }

    // 执行广度优先搜索(一层一层搜索)
    int ans = 0;
    while(!Q.empty()){
        ++ans;
        int size = Q.size();
        // 每一层搜索
        for(int i=0; i<size; ++i){
            auto unit_node = Q.front();
            Q.pop();
            int y = unit_node.first;
            int x = unit_node.second;
            for(int j=0; j<4; ++j){
                int new_y = y + dy_dx[j][0];
                int new_x = x + dy_dx[j][1];
                if (new_y >= 0 && new_y < m && 
                    new_x >= 0 && new_x < n &&
                    matrix[new_y][new_x] > matrix[y][x]){
                    --out_degrees[new_y][new_x];
                    if (out_degrees[new_y][new_x] == 0)
                        Q.push({new_y, new_x});    
                }
            }
        }
    }
    return ans;
}

欢迎交流，批评指针！