力扣931. 下降路径最小和

本文主要是介绍力扣931. 下降路径最小和，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

动态规划

• 思路：
  • 假设 dp[i][j] 为坐标 (i, j) 的路径最小和；
  • 则 dp[i][j] 上一状态：
    • dp[i - 1][j] （上一行正上方）
    • dp[i - 1][j - 1]（上一行的左侧）
    • dp[i - 1][j + 1]（上一行的右侧）
  • 所以状态方程为：
    • dp[i][j] = min(dp[i - 1][j], dp[i - 1][j - 1], dp[i - 1][j + 1]) + matrix[i][j]
  • 注意边界，第一列和最后一列只有上一列两侧是否有效；
  • dp[0][j] 为 matrix 第一行元素；

class Solution {
public:int minFallingPathSum(vector<vector<int>>& matrix) {int n = matrix.size();std::vector<std::vector<int>> dp(n, std::vector<int>(n));std::copy(matrix[0].begin(), matrix[0].end(), dp[0].begin());for (int i = 1; i < n; ++i) {for (int j = 0; j < n; ++j) {// upint dp1 = dp[i - 1][j];if (j > 0) {// top leftdp1 = std::min(dp1, dp[i - 1][j - 1]);}if (j < n - 1) {// top rightdp1 = std::min(dp1, dp[i - 1][j + 1]);}dp[i][j] = dp1 + matrix[i][j];}}return *std::min_element(dp[n - 1].begin(), dp[n - 1].end());}
};

————————————————————————————————————————

这篇关于力扣931. 下降路径最小和的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---