百度智能小程序_层次化网络设计的优点是什么_windows优化大师怎么卸载_嘉峪关seo

原题链接：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;}
};