溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
小編給大家分享一下golang刷leetcode動態規劃之如何求最小路徑和，希望大家閱讀完這篇文章之后都有所收獲，下面讓我們一起去探討吧！
給定一個包含非負整數的 m x n 網格，請找出一條從左上角到右下角的路徑，使得路徑上的數字總和為最小。
說明：每次只能向下或者向右移動一步。
示例:
輸入:
[ [1,3,1], [1,5,1], [4,2,1]]
輸出: 7
解釋: 因為路徑 1→3→1→1→1 的總和最小。
解題思路
1,這也是一個典型的動態規劃題
2，是遞增的
3，狀態轉移方程為
if step[i-1][j]<step[i][j-1]{ step[i][j]=step[i-1][j]+grid[i][j]}else{ step[i][j]=step[i][j-1]+grid[i][j]}
歸納總結
1，這種矩陣尋找路徑類型的題目基本都是動態規劃題目
2，動態規劃問題都可以遞歸解，只不過利用空間換時間，存儲了最優子結構
3，動態規劃主要考察的是問題拆分能力，將一個問題拆分為一個個小問題，然后各個擊破。
代碼實現
func minPathSum(grid [][]int) int { if len(grid)==0{ return 0 } step:=make([][]int,len(grid)) for i:=0;i<len(grid);i++{ step[i]=make([]int,len(grid[0])) } step[0][0]=grid[0][0] for i:=1;i<len(grid);i++{ step[i][0]=step[i-1][0]+grid[i][0] } for i:=1;i<len(grid[0]);i++{ step[0][i]=step[0][i-1]+grid[0][i] } for i:=1;i<len(grid);i++{ for j:=1;j<len(grid[0]);j++{ if step[i-1][j]<step[i][j-1]{ step[i][j]=step[i-1][j]+grid[i][j] }else{ step[i][j]=step[i][j-1]+grid[i][j] } } } return step[len(grid)-1][len(grid[0])-1]}
看完了這篇文章，相信你對“golang刷leetcode動態規劃之如何求最小路徑和”有了一定的了解，如果想了解更多相關知識，歡迎關注億速云行業資訊頻道，感謝各位的閱讀！
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
