LeetCode64-最小路径和
LeetCode64-最小路径和
给定一个包含非负整数的 m x n 网格,请找出一条从左上角到右下角的路径,使得路径上的数字总和为最小。
说明:每次只能向下或者向右移动一步。
示例:
输入:
[
[1,3,1],
[1,5,1],
[4,2,1]
]
输出: 7
解释: 因为路径 1→3→1→1→1 的总和最小。
一、思路
之前的题目,在没有给定权重的情况下,是可以用动态规划来解决的,那么这道题目可以吗?
设是从左上角移动到处的最小代价,考虑右下角的,能移动到的方法也无非就两种:
- 从向下移动一步
- 从向右移动一步
因此移动到处的最小代价:
根据上述状态转移方程,即可解得。
C++代码:
class Solution {
public:
int minPathSum(vector<vector<int>>& grid) {
if (grid.empty()||grid[0].empty())
return 0;
vector<vector<long long>> dp(grid.size(), vector<long long>(grid[0].size()));
// 初始化初始条件
dp[0][0] = grid[0][0];
for (int i = 1; i < grid.size(); i++)
dp[i][0] = grid[i][0] + dp[i - 1][0];
for (int j = 1; j < grid[0].size(); j++)
dp[0][j] = grid[0][j] + dp[0][j - 1];
// 计算状态转移方程
for (int i = 1; i < grid.size(); i++)
for (int j = 1; j < grid[0].size(); j++)
dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];
return dp[grid.size() - 1][grid[0].size() - 1];
}
long long min(long long& a, long long& b) {
return (a > b) ? b : a;
}
};
执行效率: