[LeetCode]Minimum Path Sum

简单的DP题，DP方程：

• dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j]

假设input矩阵，高n宽m，用滚动数组可以把空间优化到O(m)，时间复杂度O(m * n)，代码如下：

	class Solution {
	public:
	int minPathSum(vector<vector<int>>& grid) {
	int m = grid.size(), n = m? grid[0].size(): 0;
	vector<int> dp(n + 1, INT_MAX);
	dp[0] = 0;
	//dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j]
	for(int i = 0; i < m; ++i)
	{
	for(int j = 0; j < n; ++j)
	{
	dp[j + 1] = min(dp[j], dp[j + 1]) + grid[i][j];
	}
	dp[0] = INT_MAX;
	}
	return dp[n];
	}
	};

view raw Minimum Path Sum.cpp hosted with ❤ by GitHub