前言

動(dòng)規(guī)五部曲

1.確定dp數(shù)組含義

2.確定遞推公式

3.初始化數(shù)組

4.確定遍歷方式

5.打印dp數(shù)組查看分析問題

LeetCode? T62 不同路徑

題目鏈接:62. 不同路徑 - 力扣（LeetCode）

題目思路:

注:n行m列而不是m行n列

1.確定dp數(shù)組含義

代表到達(dá)此下標(biāo)有多少條路徑

2.確定遞推公式

因?yàn)橹荒芟蛴一蛘呦蛳伦?所以到達(dá)i,j這個(gè)點(diǎn)的路徑只有從左邊和從上面到達(dá),所以到達(dá)這個(gè)的途徑數(shù)就是左邊的數(shù)和上面的數(shù)之和.

dp[i][j] = dp[i-1][j] + dp[i][j-1];

3.初始化數(shù)組

初始化的時(shí)候應(yīng)該將左邊邊界和上面邊界都初始化為1,因?yàn)橹挥幸粭l路徑能到達(dá)

        for(int i = 0;i<m;i++){
            dp[i][0] = 1;
        }
        for(int i = 0;i<n;i++){
            dp[0][i] = 1;
        }

4.確定遍歷方式

此題目跟遍歷順序無關(guān),順序遍歷即可

5.打印dp數(shù)組查看分析問題

遇見問題可以打印dp數(shù)組并推導(dǎo)嘗試是否有問題

最后直接返回右下角的值即可

題目代碼:

class Solution {
    public int uniquePaths(int m, int n) {
        int[][] dp = new int[m][n];
        for(int i = 0;i<m;i++){
            dp[i][0] = 1;
        }
        for(int i = 0;i<n;i++){
            dp[0][i] = 1;
        }
//記得從下標(biāo)1,1開始哦,不然就越界了
        for(int i = 1;i<m;i++){
            for(int j = 1;j<n;j++){
                dp[i][j] = dp[i-1][j] + dp[i][j-1];
            }
        }
        return dp[m-1][n-1];
    }
}

LeetCode T63 不同路徑II

題目鏈接:63. 不同路徑 II - 力扣（LeetCode）

題目思路:

1.確定dp數(shù)組含義

此時(shí)的dp數(shù)組也是代表和上一題一樣的含義,表示有多少條路徑能到達(dá)這個(gè)坐標(biāo)

2.確定遞推公式

注:這里如果遇到障礙,也就是1的情況,我們就讓dp這個(gè)點(diǎn)取得0,不然就是和上文一樣的遞推公式

dp[i][j] = (obstacleGrid[i][j] == 0)?dp[i-1][j] + dp[i][j-1]:0;

3.初始化數(shù)組

這里初始化在邊界遇到障礙的時(shí)候就是代表后面的下標(biāo)都是到達(dá)不了的地方,所以就不進(jìn)行賦值

注意:如果起點(diǎn)或者終點(diǎn)為障礙,就直接返回0

4.確定遍歷方式

順序遍歷即可文章來源地址http://www.zghlxwxcb.cn/news/detail-736931.html

5.打印dp數(shù)組查看分析問題

題目代碼:

class Solution {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int m = obstacleGrid.length;
        int n = obstacleGrid[0].length;
        int[][] dp = new int[m][n];
        //起點(diǎn)和終點(diǎn)為障礙
        if(obstacleGrid[0][0] == 1 || obstacleGrid[m-1][n-1] == 1){
            return 0;
        }
        for(int i = 0;i<m && obstacleGrid[i][0] == 0;i++){
            dp[i][0] = 1;
        }
        for(int i = 0;i<n && obstacleGrid[0][i] == 0;i++){
            dp[0][i] = 1;
        }
        for(int i = 1;i<m;i++){
            for(int j = 1;j<n;j++){
                dp[i][j] = (obstacleGrid[i][j] == 0)?dp[i-1][j] + dp[i][j-1]:0;
            }
        }
        return dp[m-1][n-1];

    }
}

到了這里，關(guān)于代碼隨想錄Day33 LeetCode T62不同路徑 LeetCode T63 不同路徑II的文章就介紹完了。如果您還想了解更多內(nèi)容，請?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！