小編給大家分享一下golang刷leetcode動態(tài)規(guī)劃之如何解決不同路徑問題，希望大家閱讀完這篇文章之后都有所收獲，下面讓我們一起去探討吧！

創(chuàng)新互聯(lián)是一家專業(yè)提供望奎企業(yè)網(wǎng)站建設(shè),專注與成都網(wǎng)站制作、網(wǎng)站建設(shè)、H5開發(fā)、小程序制作等業(yè)務(wù)。10年已為望奎眾多企業(yè)、政府機構(gòu)等服務(wù)。創(chuàng)新互聯(lián)專業(yè)的建站公司優(yōu)惠進行中。

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

機器人每次只能向下或者向右移動一步。機器人試圖達到網(wǎng)格的右下角（在下圖中標記為“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 

看完了這篇文章，相信你對“golang刷leetcode動態(tài)規(guī)劃之如何解決不同路徑問題”有了一定的了解，如果想了解更多相關(guān)知識，歡迎關(guān)注創(chuàng)新互聯(lián)行業(yè)資訊頻道，感謝各位的閱讀！