动态规划

• 思路：
  • 假设 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) {
                // up
                int dp1 = dp[i - 1][j];
                if (j > 0) {
                    // top left
                    dp1 = std::min(dp1, dp[i - 1][j - 1]);
                }
                if (j < n - 1) {
                    // top right
                    dp1 = 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());
    }
};

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