?? 算法刷題專欄 | 面試必備算法 | 面試高頻算法 ??
?? 越難的東西,越要努力堅(jiān)持，因?yàn)樗哂泻芨叩膬r(jià)值，算法就是這樣?
?? 作者簡(jiǎn)介：碩風(fēng)和煒，CSDN-Java領(lǐng)域新星創(chuàng)作者??，保研|國(guó)家獎(jiǎng)學(xué)金|高中學(xué)習(xí)JAVA|大學(xué)完善JAVA開發(fā)技術(shù)棧|面試刷題|面經(jīng)八股文|經(jīng)驗(yàn)分享|好用的網(wǎng)站工具分享??????
?? 恭喜你發(fā)現(xiàn)一枚寶藏博主,趕快收入囊中吧??
?? 人生如棋，我愿為卒，行動(dòng)雖慢，可誰(shuí)曾見我后退一步？????

?? 知識(shí)回顧

大家在學(xué)習(xí)這道題目之前，可以先去看一下我之前寫過(guò)的一篇和這個(gè)題目類似有類似求解思路的博客，再看這個(gè)題目就更容易理解了。
博客的地址放到這里了，可以先去學(xué)習(xí)一下這到題目。

• 【LeetCode: 62. 不同路徑 | 暴力遞歸=＞記憶化搜索=＞動(dòng)態(tài)規(guī)劃 】

?? 題目鏈接

• 64. 最小路徑和

? 題目描述

給定一個(gè)包含非負(fù)整數(shù)的 m x n 網(wǎng)格 grid ，請(qǐng)找出一條從左上角到右下角的路徑，使得路徑上的數(shù)字總和為最小。

說(shuō)明：每次只能向下或者向右移動(dòng)一步。

示例 1：

輸入：grid = [[1,3,1],[1,5,1],[4,2,1]]
輸出：7
解釋：因?yàn)槁窂?1→3→1→1→1 的總和最小。

示例 2：

輸入：grid = [[1,2,3],[4,5,6]]
輸出：12

提示：

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

?? 求解思路&實(shí)現(xiàn)代碼&運(yùn)行結(jié)果

? 暴力法-DFS

?? 求解思路

1. 這道題目的求解思路比較簡(jiǎn)單，從左上角0,0位置出發(fā)，每次只能向右走或者向下走，到右下角m-1,n-1的路徑最小和是多少。
2. 那么我們直接通過(guò)遞歸-DFS求解即可。

?? 實(shí)現(xiàn)代碼

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

?? 運(yùn)行結(jié)果

時(shí)間超限了，不要緊張，我們來(lái)繼續(xù)優(yōu)化它！

? 記憶化搜索

?? 求解思路

1. 因?yàn)樵谶f歸的過(guò)程中，會(huì)重復(fù)的出現(xiàn)一些多次計(jì)算的結(jié)果，我們通過(guò)開辟一個(gè)數(shù)組，將結(jié)果提前緩存下來(lái)，算過(guò)的直接返回，避免重復(fù)計(jì)算，通過(guò)空間來(lái)去換我們的時(shí)間。

?? 實(shí)現(xiàn)代碼

class Solution {

    private int[][] dp;

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

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

?? 運(yùn)行結(jié)果

我們發(fā)現(xiàn)，通過(guò)加一個(gè)緩存表，時(shí)間復(fù)雜度發(fā)生了翻天覆地的變化，真是不可思議！

? 動(dòng)態(tài)規(guī)劃

?? 求解思路

1. 有了遞歸，有了記憶化搜索，接下來(lái)就是動(dòng)態(tài)規(guī)劃了，直接上手。

?? 實(shí)現(xiàn)代碼

class Solution {

    private int[][] dp;

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

?? 運(yùn)行結(jié)果

搞定！

?? 共勉

文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-453561.html

到了這里，關(guān)于【LeetCode:64. 最小路徑和 | 暴力遞歸=＞記憶化搜索=＞動(dòng)態(tài)規(guī)劃 】的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！