Go 刷 LeetCode 系列:動態(tài)規(guī)劃(9)不同路徑 II

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

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

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

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

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

示例 1:

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

解題思路
1，這是一個典型的動態(tài)規(guī)劃題

2，子問題拆分：由于每個點只能從左往右或者從上往下

? ? ? ??遞推公式為m[i][j]=m[i-1][j]+m[i][j-1]，由于用到了i-1,j-1所以i，j均遞增

?3，如果有路障

m[i][j]=0

4，邊界問題

如果左上角為1則m[0][0]=0,否則為1

5，最上水平的位置只能從左往右，最左垂直位置只能從上往下

故 m[i][0]=m[i-1][0],m[0][j]=m[0][j-1]

如果有路障?m[i][0]=0,m[0][j]=0

func uniquePathsWithObstacles(obstacleGrid [][]int) int {    if len(obstacleGrid)==0{        return 0    }    m:=make([][]int,len(obstacleGrid))    for i:=0;i<len(obstacleGrid);i++{        m[i]=make([]int,len(obstacleGrid[0]))    }    if obstacleGrid[0][0]==1{        return 0    }    m[0][0]=1    for i:=1;i<len(obstacleGrid);i++{     if obstacleGrid[i][0]==1{       m[i][0]=0     }else{        m[i][0]=m[i-1][0]     }    }    for j:=1;j<len(obstacleGrid[0]);j++{      if obstacleGrid[0][j]==1{          m[0][j]=0       }else{          m[0][j]=m[0][j-1]        }     }    for i:=1;i<len(obstacleGrid);i++{        for j:=1;j<len(obstacleGrid[0]);j++{            if obstacleGrid[i][j]==1{                    m[i][j]=0                }else{                    m[i][j]=m[i-1][j]+m[i][j-1]                }        }    }    return m[len(obstacleGrid)-1][len(obstacleGrid[0])-1]}

推薦閱讀

• Go 刷 LeetCode 系列：動態(tài)規(guī)劃（8）盈利計劃
  

喜歡本文的朋友，歡迎關(guān)注“Go語言中文網(wǎng)”：

Go語言中文網(wǎng)啟用微信學(xué)習(xí)交流群，歡迎加微信：274768166，投稿亦歡迎