[LeetCode]Minimum Falling Path Sum

动态规划的题目，如果我们用dp[i][j]表示结尾于(从下到上)i和j处的最大值，我们有递推公式:

• dp[i][j] = min(dp[i + 1][j], dp[i + 1][j - 1], dp[i + 1][j + 1]) + A[i][j], where 0 < j < n - 1, n为列数
• dp[i][j] = min(dp[i + 1][j],  dp[i + 1][j + 1]) + A[i][j], where j == 0
• dp[i][j] = min(dp[i + 1][j],  dp[i + 1][j - 1]) + A[i][j], where j == n - 1, n为列数

我们不需要额外的空间，因为我们可以在原矩阵上进行DP。代码如下:

	class Solution {
	public:
	int minFallingPathSum(vector<vector<int>>& A) {
	int m = A.size(), n = m ? A[0].size() : 0, res = INT_MAX;
	for (int i = m - 1; i >= 0; --i)
	{
	for (int j = 0; j < n; ++j)
	{
	if (i < m - 1)
	{
	int curr = A[i + 1][j];
	if (j)curr = min(curr, A[i + 1][j - 1]);
	if (j < n - 1) curr = min(curr, A[i + 1][j + 1]);
	A[i][j] += curr;
	}
	if (!i)res = min(res, A[i][j]);
	}
	}
	return res;
	}
	};

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