题目
给定m*n矩阵。存储当下节点的权重，求解从左上角到达右下角，所经过的路径的最小权重
分析
DP思想实现，dp[i][j]存储从[0][0]到达[i][j]所经历的路径的最小权重和
具体思路见代码注释处
C++代码实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
|
*Use DP
* dp[i][j] from [0][0] to [i][j], The min sum of all numbers along this path.
* dp[i][j] = grid[i][j] if i == 0 && j == 0
* = grid[i][j-1] + grid[i][j] if j == 0 && i != 0
* = grid[i-1][j] + grid[i][j] if i == 0 && j != 0
* = min(dp[i-1][j] + dp[i][j-1]) + grid[i][j] if i != 0 && j != 0
*/
class Solution {
public:
int (vector<vector<int>>& grid) {
vector<vector<int>> res = grid;
int min_num = 0;
for(int i = 0; i < grid.size(); i++){
for(int j = 0; j < grid[i].size(); j++){
if(i == 0 && j == 0){
min_num = res[i][j] = grid[i][j];
}
else if(i == 0){
min_num = res[i][j] = res[i][j-1] + grid[i][j];
}
else if(j == 0){
min_num = res[i][j] = res[i-1][j] + grid[i][j];
}
else{
min_num = res[i][j] = min(res[i-1][j], res[i][j-1]) + grid[i][j];
}
}
}
return min_num;
}
};
|
近期评论