力扣——动态规划

矩阵中的最长递增路径

题目

329. 矩阵中的最长递增路径 - 力扣（LeetCode）

思路

刚开始的思路是直接dfs暴力搜，然后时间超限了。

仔细思考了一下，主要是做了很多重复计算，那就可以用记忆化搜索来优化。

为了避免重复计算路径长度，我们可以使用一个数组，将已经计算过的路径长度保存起来。当我们再次访问到同一个位置时，直接使用之前计算好的结果，而不是重新计算。这将大大降低时间复杂度。

使用记忆化搜索将时间复杂度降为 O(m×n)，其中 m 和n 是矩阵的行数和列数

代码

优化前

public int longestIncreasingPath(int[][] matrix) {
        int max = Integer.MIN_VALUE;
        boolean[][] visited = new boolean[matrix.length][matrix[0].length];
        for(int i = 0; i < matrix.length; i++) {
            for(int j = 0; j < matrix[i].length; j++) {
                visited[i][j] = true;
                max = Math.max(max,fun(matrix,i,j,visited));
                visited[i][j] = false;
            }
        }
        return max;
    }

    private int fun(int[][] matrix, int x, int y,boolean[][] visited) {
        int[] a = {0,0,1,-1};
        int[] b = {1,-1,0,0};
        int MAX = 0;
        for(int i = 0; i <4; i++) {
            int xx = a[i]+x;
            int yy = b[i]+y;
            if(xx>=0&&xx<matrix.length&&yy>=0&&yy<matrix[0].length) {
                if(matrix[xx][yy]>matrix[x][y] && !visited[xx][yy]) {
                    visited[xx][yy] = true;
                    MAX = Math.max(fun(matrix,xx,yy,visited),MAX);
                    visited[xx][yy] = false;
                }
            }
        }
        return MAX+1;
    }

优化后

public int longestIncreasingPath(int[][] matrix) {
        int max = Integer.MIN_VALUE;
        int[][] visited = new int[matrix.length][matrix[0].length];
        for(int i = 0; i < matrix.length; i++) {
            for(int j = 0; j < matrix[i].length; j++) {
                max = Math.max(max,fun(matrix,i,j,visited));
            }
        }
        return max;
    }

    private int fun(int[][] matrix, int x, int y,int[][] visited) {
        if(visited[x][y] != 0) return visited[x][y];
        int[] a = {0,0,1,-1};
        int[] b = {1,-1,0,0};
        int MAX = 0;
        for(int i = 0; i <4; i++) {
            int xx = a[i]+x;
            int yy = b[i]+y;
            if(xx>=0&&xx<matrix.length&&yy>=0&&yy<matrix[0].length) {
                if(matrix[xx][yy]>matrix[x][y]) {
                    MAX = Math.max(fun(matrix,xx,yy,visited),MAX);
                }
            }
        }
        visited[x][y] = MAX+1;
        return MAX+1;
    }

青蛙过河

题目

403. 青蛙过河 - 力扣（LeetCode）

思路

我们使用一个哈希表 map 来存储状态：

• 键（key）：石子编号，表示位置。
• 值（value）：一个集合，存储从其他石子跳到该石子的所有步长

对于每个石子 stone 和它的可能步长集合 steps，考虑下一跳：

• 计算下一步的步长：
  • 可能的步长为：step - 1, step, step + 1。
  • 步长有效性检查：步长必须大于 0，才能向前跳。
• 计算下一块石子的位置：
  • 用当前石子位置 stone 加上步长，得到下一块石子的编号 num= x+ num。
• 更新状态：
  • 如果 num是一个有效的石子（存在于 stones 中），将 num添加到 map集合 中。
• 判断终止条件
  • 当处理到最后一块石子时，如果它的步长集合非空，说明青蛙可以跳到最后的石子上；否则说明无法过河。

代码

 public boolean canCross(int[] stones) {
        Map<Integer, HashSet<Integer>> map = new HashMap<>();
        for(int x:stones){
            map.put(x,new HashSet<>());
        }
        map.get(0).add(0);
        for(int x:stones){
            for(int step:map.get(x)){
                int[] sum = {step-1,step,step+1};
                for(int num:sum){
                    if(num>0&&map.containsKey(x+num)){
                        map.get(x+num).add(num);
                    }
                }
            }
        }
        if(map.get(stones[stones.length-1]).isEmpty()){
            return false;
        }
        return true;
    }