题目

https://oj.leetcode.com/problems/minimum-path-sum/

分析

动态规划题，

某一点的MinimumPathSum = min(左侧点的MinimumPathSum, 上侧点的MinimumPathSum) + 该点的数值

不过第一行和第一列的MinimumPathSum有些特殊，需要单独处理一下。

代码

class Solution
{
public:
	int minPathSum(vector<vector<int>> &grid)
	{
		int m = grid.size();
		int n = grid[0].size();
		vector<vector<int>> res(grid);

		//First row and first col 's Minimum Path Sum
		for (int i = 1; i < m; i++)
			res[i][0] += res[i-1][0];
		for (int i = 1; i < n; i++)
			res[0][i] += res[0][i-1];

		//Other points's Minimum Path Sum
		for (int i = 1; i < m; i++)
			for (int j = 1; j < n; j++)
				res[i][j] += min(res[i-1][j], res[i][j-1]);

		return res[m-1][n-1];
	}
};

本文章迁移自http://blog.csdn.net/timberwolf_2012/article/details/40868907