難度：中等
頻次：54
題目：給定一個(gè)包含非負(fù)整數(shù)的 m x n 網(wǎng)格 grid ，請找出一條從左上角到右下角的路徑，使得路徑上的數(shù)字總和為最小。
說明：每次只能向下或者向右移動(dòng)一步。

解題思路：動(dòng)態(tài)規(guī)劃
注意：

• 為什么使用動(dòng)態(tài)規(guī)劃呢？—>求最值，并且不求過程，有很明顯的狀態(tài)轉(zhuǎn)移方程
• 主要把情況分為4種情況
  • 在左邊的邊界的時(shí)候，即j==0的情況，總和應(yīng)該為上面的總和+該位置的值
  • 在上邊的邊界的時(shí)候，即i==0的時(shí)候，總和應(yīng)該為左邊的總和+該位置的值
  • 在左邊的邊界+在上邊邊界的時(shí)候，即i0&&j0的時(shí)候，總和為該位置的值即起點(diǎn)的值
  • 其他的情況 ，都有兩種可能性，即取兩種可能性的最小值+該位置的值
• 如果為了追求節(jié)省空間，也可以把步設(shè)置額外的dp，直接把存放在grid里

代碼：

class Solution {public int minPathSum(int[][] grid) {int col=grid[0].length;int row=grid.length;int[][] dp=new int[row][col];for(int i=0;i<row;i++){for(int j=0;j<col;j++){if(i==0&&j==0) dp[i][j]=grid[i][j];else if(i==0) dp[i][j]=dp[i][j-1]+grid[i][j];else if(j==0) dp[i][j]=dp[i-1][j]+grid[i][j];else {dp[i][j]=Math.min(dp[i-1][j],dp[i][j-1])+grid[i][j];}}}return dp[row-1][col-1];} }

總結(jié)

以上是生活随笔為你收集整理的leetcode 64. 最小路径和的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。