题目描述
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.
Example:
Input: <br> [ <br> [1,3,1], <br> [1,5,1], <br> [4,2,1] <br> ] <br> Output: 7 <br> Explanation: <br> Because the path 1→3→1→1→1 minimizes the sum. <br>
Note:
- You can only move either down or right at any point in time.
dp解题思路
- 主要是填一个二维表格，dp递归式为dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j]
- 最后返回dp[i][j]
C++代码
class Solution {
public:
int res = 0;
int minPathSum(vector<vector<int>>& grid) {
if(grid.size() == 0){
return 0;
}
int row = grid.size();
int col = grid[0].size();
int dp[row][col] = {0};
dp[0][0] = grid[0][0];
for(int i = 1; i < col; i++){
dp[0][i] = grid[0][i] + dp[0][i - 1];
}
for(int i = 1; i < row; i++){
dp[i][0] = grid[i][0] + dp[i - 1][0];
}
for(int i = 1; i < row; i++){
for(int j = 1; j < col; j++){
dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];
}
}
return dp[row - 1][col - 1];
}
};
0205第二遍解题
- 首先类似于机器人路径 只能往右往下移动 总共有多少路径
- 注意这道题的区别 是最后的sum最小
- 这里初始化的时候就需要注意 行里元素初始化时 与当前元素的 前一行/列元素初始化时有关 （进行累加）
- 然后 dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j]
C++代码
class Solution {
public:
int minPathSum(vector<vector<int>>& grid) {
int row = grid.size();
int col = grid[0].size();
int dp[row][col] = {0};
dp[0][0] = grid[0][0];
for(int i = 1; i < col; i++){
dp[0][i] = dp[0][i - 1] + grid[0][i];
}
for(int i = 1; i < row; i++){
dp[i][0] = dp[i - 1][0] + grid[i][0];
}
for(int i = 1; i < row; i++){
for(int j = 1; j < col; j++){
dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];
}
}
return dp[row - 1][col - 1];
}
};
