牛客NC138-矩阵最长递增路径

题目链接

描述

给定一个 行 列矩阵，矩阵内所有数均为非负整数。

求一条路径，该路径上所有数是递增的。

这个路径必须满足以下条件：

1. 对于每个单元格，你可以往上，下，左，右四个方向移动。 你不能在对角线方向上移动或移动到边界外。

2. 你不能走重复的单元格。即每个格子最多只能走一次。

数据范围：

1≤≤1000

0≤≤1000

方法一：直接DFS

解题思路：

我们对矩阵中的每一个元素进行,即从每一个点出发，向着周围所有比当前小的节点前进，并不断更新返回值。这样就能找出最长的增广路径。

图解

代码

import java.util.*;


public class Solution {
    public int[][] f = {{0,1}, {1, 0}, {0, -1}, {-1, 0}};    // 方向数组，表示上下左右的[x,y]向量
    public int solve (int[][] matrix) {
        int ans = 0;
        for(int i = 0; i < matrix.length; i++){    // 对每个元素进行dfs
            for(int j = 0; j < matrix[i].length; j++){
                ans = Math.max(ans, dfs(matrix, i, j, -1));
            }
        }
        return ans;
    }

    private int dfs (int[][] matrix, int i, int j, int pre){    // pre为走到该节点的上一个节点的值
        if(matrix[i][j] <= pre){    // 确保当前节点比上一个大，
            return 0;
        }
        int res = 0;
        for(int k = 0; k < 4; ++k){    // 上下左右四个方向
            int tmpi = i + f[k][0];
            int tmpj = j + f[k][1];

            // 在允许范围内
            if(tmpi >= 0 && tmpj >= 0 && tmpi < matrix.length && tmpj < matrix[i].length){
                res = Math.max(res, dfs(matrix, i + f[k][0], j + f[k][1], matrix[i][j]));
            }
        }
        return res + 1;    // 加上当前节点
    }
}

复杂度分析

• 时间复杂度每个点都要一次

• 空间复杂度只需在原数组上操作

方法二：记忆化搜索

解题思路

我们在方法一的思路下优化，我们每次的过程中一定能得到当前路径下的子元素的最长增广路径，所以我们可以用同样一个数组将其保存下来，当有别的节点需要经过该节点时我们可以直接得出结果返回，这样就能起到一个剪枝的作用，避免通过一条路做多次的情况。

图解

代码

import java.util.*;


public class Solution {
    private int[][] f = {{0,1}, {1, 0}, {0, -1}, {-1, 0}};// 方向数组，表示上下左右的[x,y]向量
    private int[][] dp;// 用来记录当前元素的最长增广路径
    public int solve (int[][] matrix) {
        dp = new int[matrix.length][matrix[0].length];
        int ans = 0;
        for(int i = 0; i < matrix.length; i++){
            for(int j = 0; j < matrix[i].length; j++){
                ans = Math.max(ans, dfs(matrix, i, j, -1));
            }
        }
        return ans;
    }

    private int dfs (int[][] matrix, int i, int j, int pre){// pre为走到该节点的上一个节点的值
        if(matrix[i][j] <= pre){    // 小于的话不用走了
            return 0;
        }
        if(dp[i][j] > 0){    // 如果dp数组对于该位置有记录直接拿出来用
            return dp[i][j];
        }
        int res = 0;
        // dp数组没有记录的话就要dfs
        for(int k = 0; k < 4; ++k){    // 上下左右四个方向
            int tmpi = i + f[k][0];
            int tmpj = j + f[k][1];
            if(tmpi >= 0 && tmpj >= 0 && tmpi < matrix.length && tmpj < matrix[i].length){
                res = Math.max(res, dfs(matrix, i + f[k][0], j + f[k][1], matrix[i][j]));
            }
        }
        return dp[i][j] = res + 1;
    }
}

复杂度分析

• 时间复杂度的过程只要每个点经过一次就不会再经过。

• 空间复杂度dp数组大小为,为矩阵的长或宽。