【LeetCode: 剑指 Offer II 099. 最小路径之和 | 暴力递归 | DFS =＞记忆化搜索=＞动态规划】

目录

• • 题目链接
  • 题目描述
  • 求解思路&实现代码&运行结果
  • • 暴力递归 | DFS
    • 记忆化搜索
    • 动态规划
  • 共勉

题目链接

剑指 Offer II 099. 最小路径之和
64. 最小路径和

题目描述

给定一个包含非负整数的 m x n 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。

说明：一个机器人每次只能向下或者向右移动一步。

提示：

m == grid.length
n == grid[i].length
1 <= m, n <= 200
0 <= grid[i][j] <= 100

求解思路&实现代码&运行结果

暴力递归 | DFS

求解思路

1. 通过读取题目的意思我们可以知道，从左上角位置开始，每次可以向下走，或者向右走，求最后到达右下角位置路径的最小值。
2. 我们可以对题目进行一个简单的分析，如果此时我们是处于最后一行的，那么下次我们只能继续向右走，同理，如果我们此时是处理最后一列的，那么下次我们只能向下走。
3. 上面是俩种特殊情况，然后是任意一个位置，任意一个位置的值可能来自左侧，也可能来自上侧，我们需要取得它们的最小值，然后加上当前位置的值，不断重复这个过程，直到目标节点。

实现代码1

注意，代码的实现方式可以有很多，大家根据自己的习惯来就好

class Solution {
    public int minPathSum(int[][] grid) {
        int m=grid.length,n=grid[0].length;
        return process(0,0,m,n,grid);
    }

    public int process(int x,int y,int m,int n,int[][] grid){
        if(x>=m||y>=n) return Integer.MAX_VALUE;
        if(x==m-1&&y==n-1) return grid[x][y];
        return Math.min(process(x,y+1,m,n,grid),process(x+1,y,m,n,grid))+grid[x][y];
    }
}

实现代码2

class Solution {
    int min=Integer.MAX_VALUE;
    public int minPathSum(int[][] grid) {
        int m=grid.length,n=grid[0].length;
        process(0,0,m,n,grid,0);
        return min;
    }

    public void process(int x,int y,int m,int n,int[][] grid,int sum){
        if(x>=m||y>=n) return;
        if(x==m-1&&y==n-1){
            min=Math.min(min,sum+grid[x][y]); 
            return;
        }
        process(x,y+1,m,n,grid,sum+grid[x][y]);
        process(x+1,y,m,n,grid,sum+grid[x][y]);
    }
}

运行结果

大家不要看到时间超限就害怕，相反，看到这个我们更应该放心，这个是我们期待的结果。

记忆化搜索

求解思路

1. 核心思路就是我们上面的求解过程，如果没有理解可以继续看上面的图解过程。
2. 在原来的基础上加缓存表，将结果进行记录，避免重复计算。

实现代码

class Solution {
    public int minPathSum(int[][] grid) {
        int m=grid.length,n=grid[0].length;
        int[][] dp=new int[m][n];
        for(int i=0;i<m;i++) Arrays.fill(dp[i],-1);
        return process(0,0,m,n,grid,dp);
    }

    public int process(int x,int y,int m,int n,int[][] grid,int[][] dp){
        if(x>=m||y>=n) return Integer.MAX_VALUE;
        if(dp[x][y]!=-1) return dp[x][y];
        if(x==m-1&&y==n-1) return dp[x][y]=grid[x][y];
        return dp[x][y]=Math.min(process(x,y+1,m,n,grid,dp),process(x+1,y,m,n,grid,dp))+grid[x][y];
    }
}

运行结果

加个缓存表就是香，通过！

动态规划

求解思路

1. 同理，核心求解思路我们上面已经讲过了，此处不同的是原来通过递归，此时我们通过dp数组和循环即可完成。

实现代码

继续改进！

class Solution {
    public int minPathSum(int[][] grid) {
        int m=grid.length,n=grid[0].length;
        int[][] dp=new int[m][n];
        dp[m-1][n-1]=grid[m-1][n-1];
        for(int i=m-2;i>=0;i--){
            dp[i][n-1]=dp[i+1][n-1]+grid[i][n-1];
        }
        for(int i=n-2;i>=0;i--){
            dp[m-1][i]=dp[m-1][i+1]+grid[m-1][i];
        }
        for(int x=m-2;x>=0;x--){
            for(int y=n-2;y>=0;y--){
                dp[x][y]=Math.min(dp[x][y+1],dp[x+1][y])+grid[x][y];
            }
        }
        return dp[0][0];
    }
}

运行结果

共勉

最后，我想送给大家一句一直激励我的座右铭，希望可以与大家共勉！