LeetCode64-最小路径和

LeetCode64-最小路径和

给定一个包含非负整数的 m x n 网格,请找出一条从左上角到右下角的路径,使得路径上的数字总和为最小。

说明:每次只能向下或者向右移动一步。

示例:

输入:
[
  [1,3,1],
  [1,5,1],
  [4,2,1]
]
输出: 7
解释: 因为路径 1→3→1→1→1 的总和最小。

一、思路

之前的题目,在没有给定权重的情况下,是可以用动态规划来解决的,那么这道题目可以吗?

f(i,j)f(i,j)是从左上角移动到(i,j)(i,j)处的最小代价,考虑右下角的(m,n)(m,n),能移动到(m,n)(m,n)的方法也无非就两种:

  • (m1,n)(m-1,n)向下移动一步
  • (m,n1)(m,n-1)向右移动一步

因此移动到(m,n)(m,n)处的最小代价:

f(i,j)=cost(i,j)+min(f(m1,n)f(m,n1))f(i,j)=cost(i,j)+min(f(m-1,n),f(m,n-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;
	}
};

执行效率:
LeetCode64-最小路径和