[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。代码如下: