`
bcyy
  • 浏览: 1809497 次
文章分类
社区版块
存档分类
最新评论

LeetCode Minimum Path Sum

 
阅读更多

Minimum Path Sum

Given amxngrid filled with non-negative numbers, find a path from top left to bottom right whichminimizesthe sum of all numbers along its path.

Note:You can only move either down or right at any point in time.

这个问题相当于寻宝问题Unique paths问题的加权版本。

每个格子的数字可以想象成为消耗的时间或者金钱,要寻找最佳路径,是的消耗最小。

连所有路径都能寻找到,还会怕找不到最优路径吗?呵呵。

不过要会利用动态规划法,从地往上逐步填表。

这里只使用一维表,如果使用二维表,会简单点。

注意填表不要填错了,下面注有向下走向右走的地方需要格外小心。

填写的时候要清楚,每个格子代表什么含义。
比如当前格子是table[i]; 那么table[i]代表下一行这个格(由下往上填表)的最优路径,如果是二维表就好理解点,比如当前格是table[r][i],那么我们就可以利用table[r+1][i]代表格子[r+1][i]的最优路径了。
table[i+1]代表往右一列这一格的最优路径。二维表表示:当前格是table[r][i], 那么table[r][i+1]代表格子[r][i+1]最优路径。


class Solution {
public:
	int minPathSum(vector<vector<int> > &grid) {
		int r = grid.size();
		if (r < 1) return 0;
		int c = grid[0].size();

		vector<int> table(c);

		if (c-1>=0)
			table[c-1] = grid[r-1][c-1];

		for (int i = c-2; i >= 0; i--)
		{
			table[i] = table[i+1] + grid[r-1][i];
		}

		for (int i = r-2; i >= 0; i--)
		{
			//最后一列只能往下走了,所以特殊处理一下
			table[c-1] += grid[i][c-1];
			for (int j = c-2; j >=0; j--)
			{
				//向右走
				if (table[j] <= table[j+1])
				{
					table[j] += grid[i][j];
				}
				//向下走
				else table[j] = grid[i][j] + table[j+1];
			}
		}

		return table[0];
	}
};


12.23更新一个程序,利用哨兵大大简化程序,不过理解起来稍微难点:

int minPathSum3(vector<vector<int> > &grid) 
	{
		int row = grid.size();
		if (row < 1) return 0;
		int col = grid[0].size();

		//注意:一定需要初始化为INT_MAX,否则就需要额外处理;
		vector<int> ta(col+1, INT_MAX);
		ta[col-1] = 0;//作为第一个数的启动,必须选择第一个格
		for(int i = row-1; i>=0; i--)
		{
			for (int j = col-1; j >= 0; j--)
			{
				int t = min(ta[j], ta[j+1]);
				ta[j] = t + grid[i][j];
			}
		}
		return ta[0];
	}

//2014-2-8
	int minPathSum(vector<vector<int> > &grid) 
	{
		if (grid.empty() || grid[0].empty()) return 0;
		//小心初始化好
		int *A = new int[grid[0].size()+1];
		A[0] = INT_MAX; A[1] = grid[0][0];
		for (int i = 1; i < grid[0].size(); i++) A[i+1] = grid[0][i] + A[i];
		
		for (int i = 1; i < grid.size(); i++)
		{
			for (int j = 0; j < grid[0].size(); j++)
			{
				A[j+1] = min(A[j], A[j+1]) + grid[i][j];
			}
		}
		return A[grid[0].size()];
	}



分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics