Leetcode 931. 下降路径最小和 动态规划
原题链接：Leetcode 931. 下降路径最小和
class Solution {
public:
int minFallingPathSum(vector<vector<int>>& matrix) {
int m = matrix.size();
int n = matrix[0].size();
int dp[m][n];
int res = INT_MAX;
for (int j = 0; j < n; j++) {
dp[0][j] = matrix[0][j];
res = min(res, dp[0][j]);
}
if (m == 1)
return res;
res = INT_MAX;
for (int i = 1; i < m; i++) {
for (int j = 0; j < n; j++) {
dp[i][j] = dp[i - 1][j] + matrix[i][j];
if (j - 1 >= 0)
dp[i][j] = min(dp[i][j], dp[i - 1][j - 1] + matrix[i][j]);
if (j + 1 < n)
dp[i][j] = min(dp[i][j], dp[i - 1][j + 1] + matrix[i][j]);
if (i == m - 1)
res = min(res, dp[i][j]);
}
}
return res;
}
};