【動态規劃】不同的路徑

leetcode_【62】不同的路徑

1.題目描述

一個機器人位于一個 m x n 網格的左上角 （起始點在下圖中标記為“Start” ）。

機器人每次隻能向下或者向右移動一步。機器人試圖達到網格的右下角（在下圖中标記為“Finish”）。

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

2.解題思路

動态規劃

（1）初始化

• 1)從[0,0]走到[0,0]的路徑，即沒走，設

  dp[0][0] = 0

  ;
• 2)如果mn的n為1，即機器人在m1走，隻能有一條路徑，即

  dp[i][0] = 1

• 3)如果mn的m為1，即機器人在1n走，隻能有一條路徑，即

  dp[0][1] = 1

  ;

(2) 動态規劃核心算法

• 機器人每次隻能向下或者向右移動一步。即機器人arr[i][j]的路徑由arr[i-1][j]和arr[i][j-1]決定，即

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

  ;

3.代碼

class Solution {
 public static int uniquePaths(int m, int n) {
        if(m < 0 || n < 0)
            return 0;
        int dp[][] = new int[m][n];
        //初始化
        dp[0][0] = 0;
        //初始化列
        for(int i = 0;i<n;i++){
            dp[0][i] = 1;
        }
        //初始化行
        for(int i = 0;i<m;i++){
            dp[i][0] = 1;
        }
        //動态規劃
        for(int i =1;i<m;i++){
            for(int j = 1;j<n;j++){
                dp[i][j] = arr[i-1][j]+arr[i][j-1];
            }
        }
        return dp[m-1][n-1];
    }
}
           

4.送出記錄

leetcode_【63】不同的路徑II

1.題目描述

一個機器人位于一個 m x n 網格的左上角 （起始點在下圖中标記為“Start” ）。機器人每次隻能向下或者向右移動一步。機器人試圖達到網格的右下角（在下圖中标記為“Finish”）。

現在考慮網格中有障礙物。那麼從左上角到右下角将會有多少條不同的路徑？網格中的障礙物和空位置分别用 1 和 0 來表示。

說明：m 和 n 的值均不超過 100。

示例 1:

輸入:

  [

   [0,0,0],

   [0,1,0],

   [0,0,0]

  ]

輸出:

  2

解釋:

3x3 網格的正中間有一個障礙物。

從左上角到右下角一共有 2 條不同的路徑：

1. 向右 -> 向右 -> 向下 -> 向下
2. 向下 -> 向下 -> 向右 -> 向右

2.解題思路

如果第一個格點 obstacleGrid[0][0] 是 1，說明有障礙物，那麼機器人不能做任何移動，我們傳回結果 0。

如果 obstacleGrid[0][0] 是 0，我們初始化這個值為 1 然後繼續算法。

(1)動态規劃初始化

• 1)obstacleGrid[0][0] == 0,表示沒障礙，路徑隻有一條；

        

  dp[0][0] = 1

  ;

• 2)周遊第一行，如果有一個格點初始值為 1 ，說明目前節點有障礙物，沒有路徑可以通過,設值為 0 ；否則設這個值是前一個節點的值

        

  dp[0][j] = dp[0][j-1]

  。

• 3)周遊第一列，如果有一個格點初始值為 1 ，說明目前節點有障礙物，沒有路徑可以通過，設值為 0 ；否則設這個值是前一個節點的值

        

  dp[i][0] = obstacleGrid[i-1][0]

  。

(2) 動态規劃核心算法

• 從 obstacleGrid[1][1] 開始周遊整個數組，如果某個格點初始不包含任何障礙物，就把值賦為上方和左側兩個格點方案數之和.如果這個點有障礙物，設值為 0，這可以保證不會對後面的路徑産生貢獻。

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

3.代碼

class Solution {
      public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int row = obstacleGrid.length;
        int col = obstacleGrid[0].length;
        if(obstacleGrid[0][0] == 1 || obstacleGrid==null){
            return 0;
        }
        int dp[][] = new int[row][col];
        dp[0][0] = 1;
        //行初始化
        for(int i = 1;i<col;i++){
            dp[0][i] = obstacleGrid[0][i]==1 ? 0 : dp[0][i-1];
        }
        //列初始化
        for(int i = 1;i<row; i++){
            dp[i][0] = obstacleGrid[i][0] == 1? 0:dp[i-1][0];
        }
        //動态規劃
        for(int i = 1;i<row;i++){
            for(int j = 1;j<col;j++){
                    dp[i][j] = obstacleGrid[i][j] == 1 ? 0 : dp[i-1][j]+dp[i][j-1];
            }
        }
        return dp[row-1][col-1];
    }
}
           

4.送出記錄