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.
Example:
Input:
[
[1,3,1],
[1,5,1],
[4,2,1]
]
Output: 7
Explanation: Because the path 1→3→1→1→1 minimizes the sum.
題目解釋：就是從數(shù)組的左上角走到數(shù)組右下角的最短路徑
解法一：正向
class Solution {
public:
int minPathSum(vector<vector<int>>& grid) {
int m = grid.size();
int n = grid[0].size();
int dip[m][n]; // c++定義數(shù)組的方式,dip數(shù)組中存放grid中相應(yīng)位置的最短路徑
dip[0][0] = grid[0][0];
for(int i = 1; i < m; i++) dip[i][0] = grid[i][0]+dip[i-1][0];//把上邊緣放入
for(int j = 1; j < n; j++) dip[0][j] = grid[0][j]+dip[0][j-1];//把左邊緣放入
for(int i = 1; i < m; i++){
for(int j = 1; j < n; j++){
dip[i][j] = min(dip[i-1][j],dip[i][j-1])+grid[i][j];
}
}
return dip[m-1][n-1];
}
}
解法二：遞歸慢蜓，逆向舌劳，超時
class Solution {
public:
int minPathSum(vector<vector<int>>& grid) {
return funn(grid,grid.size()-1,grid[0].size()-1);
}
// 遞歸 超時
int funn(vector<vector<int>>& grid,int row,int col){
if(row == 0 && col == 0) return grid[0][0];// 防止到grid[0][0]處返回的是INT_MAX；
if(row >= 0 && row < grid.size()&& col >= 0 && col < grid[0].size()){
int leftmin = funn(grid,row,col-1); // 左二維數(shù)組最小和
int rightmin = funn(grid,row-1,col); // 右二維數(shù)組最小和
return min(leftmin,rightmin)+grid[row][col];
}
return INT_MAX;
}
};
