溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務(wù)條款》
您好，登錄后才能下訂單哦！
小編給大家分享一下golang刷leetcode動態(tài)規(guī)劃之如何解決不同路徑問題，希望大家閱讀完這篇文章之后都有所收獲，下面讓我們一起去探討吧！
一個機器人位于一個 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<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]}
看完了這篇文章，相信你對“golang刷leetcode動態(tài)規(guī)劃之如何解決不同路徑問題”有了一定的了解，如果想了解更多相關(guān)知識，歡迎關(guān)注億速云行業(yè)資訊頻道，感謝各位的閱讀！
免責(zé)聲明：本站發(fā)布的內(nèi)容（圖片、視頻和文字）以原創(chuàng)、轉(zhuǎn)載和分享為主，文章觀點不代表本網(wǎng)站立場，如果涉及侵權(quán)請聯(lián)系站長郵箱：is@yisu.com進行舉報，并提供相關(guān)證據(jù)，一經(jīng)查實，將立刻刪除涉嫌侵權(quán)內(nèi)容。
億速云公眾號
手機網(wǎng)站二維碼