Given a?m?x?n?grid filled with non-negative numbers, find a path from top left to bottom right which?minimizes?the sum of all numbers along its path.

Note:?You can only move either down or right at any point in time.

采用動態規劃的方法，dp[i][j] = min(dp[i-1][j],dp[i],[j-1])+a[i][j];

1 class Solution { 2 public: 3 int minPathSum(vector<vector<int>>& grid) { 4 int m = grid.size(); 5 int n = grid[0].size(); 6 vector<vector<int> > dp(m,vector<int>(n)); 7 for(int i = 0;i < m;i++){ 8 for(int j = 0;j < n ;j++){ 9 if(i == 0){ 10 if(j == 0){//初始化 11 dp[i][j] = grid[i][j]; 12 } 13 else{//i==0 && j!=0 14 dp[i][j] = dp[i][j-1]+grid[i][j]; 15 } 16 } 17 else if(j == 0){//i!=0&& j==0 18 dp[i][j] = dp[i-1][j] + grid[i][j]; 19 } 20 else{//i,j!=0 21 dp[i][j] = min(dp[i-1][j],dp[i][j-1])+grid[i][j]; 22 } 23 24 } 25 } 26 return dp[m-1][n-1]; 27 } 28 };

?

轉載于:https://www.cnblogs.com/LaplaceAkuir/p/6264182.html

總結

以上是生活随笔為你收集整理的leetcode 64. Minimum Path Sum的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。