題目1：不同路徑（求到達(dá)右下角的所有路徑）

一個(gè)機(jī)器人位于一個(gè) m x n 網(wǎng)格的左上角 （起始點(diǎn)在下圖中標(biāo)記為 “Start” ）。

機(jī)器人每次只能向下或者向右移動(dòng)一步。機(jī)器人試圖達(dá)到網(wǎng)格的右下角（在下圖中標(biāo)記為 “Finish” ）。

問總共有多少條不同的路徑？

?

?解題思路：

1.dp[i][j]代表從0，0走到i，j的位置有多少條路徑

2.矩陣的左邊界和上邊界只能是一種走法，要么只能向下走，要么只能向右走

dp[i][0]=1;dp[0][i]=1;

3.到達(dá)矩陣其余元素的所有路徑可以從上一個(gè)元素得來，也可以從左一個(gè)元素得來，這里我們求的是到達(dá)i,j位置的所有路徑之和，所以我們只需要將上邊和左邊的路徑相加即可

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

源代碼如下：文章來源地址http://www.zghlxwxcb.cn/news/detail-625764.html

class Solution {
public:
? ? int uniquePaths(int m, int n) {
? ? ? ? vector<vector<int>> dp(m,vector<int>(n));//二維數(shù)組dp
? ? ? ? //矩陣左邊界只有一種走法，只能向下走
? ? ? ? for(int i=0;i<m;i++)
? ? ? ? {
? ? ? ? ? ? dp[i][0]=1;
? ? ? ? }
? ? ? ? //矩陣上邊界只有一種走法，只能向右走
? ? ? ? for(int i=0;i<n;i++)
? ? ? ? {
? ? ? ? ? ? dp[0][i]=1;
? ? ? ? }
? ? ? ? //dp[i][j]代表從0，0走到i，j的位置有多少條路徑
? ? ? ? //dp[i][j]要么是從上一個(gè)元素向下走得來，要么是左邊一個(gè)元素向右走得來
? ? ? ? //所以dp[i][j]=dp[i][j-1]+dp[i-1][j];
? ? ? ? for(int i=1;i<m;i++)
? ? ? ? {
? ? ? ? ? ? for(int j=1;j<n;j++)
? ? ? ? ? ? {
? ? ? ? ? ? ? ? dp[i][j]=dp[i][j-1]+dp[i-1][j];
? ? ? ? ? ? }
? ? ? ? }
? ? ? ? return dp[m-1][n-1];
? ? }
};

題目2：不同路徑（有障礙物）

一個(gè)機(jī)器人位于一個(gè) m x n 網(wǎng)格的左上角 （起始點(diǎn)在下圖中標(biāo)記為 “Start” ）。

機(jī)器人每次只能向下或者向右移動(dòng)一步。機(jī)器人試圖達(dá)到網(wǎng)格的右下角（在下圖中標(biāo)記為 “Finish”）。

現(xiàn)在考慮網(wǎng)格中有障礙物。那么從左上角到右下角將會(huì)有多少條不同的路徑？

網(wǎng)格中的障礙物和空位置分別用 1 和 0 來表示。

?輸入：obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]]
輸出：2
解釋：3x3 網(wǎng)格的正中間有一個(gè)障礙物。
從左上角到右下角一共有 2 條不同的路徑

解題思路：

1.左邊界和上邊界如果遇到障礙，則障礙后的地方到達(dá)路徑都為0

2.矩陣中其余元素判斷時(shí)，如果是障礙物，dp為0

3.動(dòng)態(tài)規(guī)劃方程：dp[i][j]=dp[i-1][j]+dp[i][j-1];

源代碼如下：

class Solution {
public:
    int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
        int m=obstacleGrid.size();//計(jì)算矩陣的行
        int n=obstacleGrid[0].size();//計(jì)算矩陣的列
        vector<vector<int>> dp(m,vector<int>(n,0));//定義動(dòng)態(tài)規(guī)劃的二維數(shù)組，初始化為0
        //如果矩陣中第一行第一列不是障礙物，則dp[0][0]=1
        if(obstacleGrid[0][0]!=1) dp[0][0]=1;
        //左邊界(每個(gè)元素只能由上邊元素得來)
        for(int i=1;i<m;i++)
        {
            //遇到障礙物就跳過，此時(shí)dp[i][0]=0
            if(obstacleGrid[i][0]==1)
            {
                continue;
            }
            dp[i][0]=dp[i-1][0];//其他情況等于上邊元素的dp，因?yàn)橹荒苡缮线呉粋€(gè)元素得來
        }
        //上邊界，同理
        for(int i=1;i<n;i++)
        {
            if(obstacleGrid[0][i]==1)
            {
                continue;
            }
            dp[0][i]=dp[0][i-1];
        }
        //非左邊界和上邊界的元素
        for(int i=1;i<m;i++)
        {
            for(int j=1;j<n;j++)
            {
                //跳過障礙物，只有在不是障礙物的情況才更新dp的值
                //動(dòng)態(tài)規(guī)劃方程：dp[i][j]=dp[i-1][j]+dp[i][j-1]
                //當(dāng)前位置的走法=上邊元素的所有路徑+左邊元素的所有路徑
                if(obstacleGrid[i][j]!=1) 
                {
                    dp[i][j]=dp[i-1][j]+dp[i][j-1];
                }
            }
        }
        //返回右下角元素
        return dp[m-1][n-1];
    }
};

到了這里，關(guān)于動(dòng)態(tài)規(guī)劃解“不同路徑問題”（所有路徑、有障礙物時(shí)的所有路徑）的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！