leetcode 931

题目：

给你一个 n x n 的 方形 整数数组 matrix ，请你找出并返回通过 matrix 的下降路径 的 最小和 。下降路径 可以从第一行中的任何元素开始，并从每一行中选择一个元素。在下一行选择的元素和当前行所选元素最多相隔一列（即位于正下方或者沿对角线向左或者向右的第一个元素）。具体来说，位置 (row, col) 的下一个元素应当是 (row + 1, col - 1)、(row + 1, col) 或者 (row + 1, col + 1) 。

输入输出

示例 1：

输入：matrix = [[2,1,3],[6,5,4],[7,8,9]]
输出：13

示例 2:

输入：matrix = [[-19,57],[-40,-5]]
输出：-59

提示：

• n == matrix.length== matrix[i].length
• 1 <= n <= 200
• -1000 <= matrix[i][j] <= 1000

思路

dp,稍微注意一下边界条件就行了

class Solution
{
public:
    int minFallingPathSum(vector<vector<int>> &matrix){
        int n = matrix.size();
        int M = INT_MAX;
        if (n == 1)
            return matrix[0][0];
        for (int i = 1; i < n; i++)
            for (int j = 0; j < n; j++)
            {
                if (j == 0)
                {
                    matrix[i][j] = min(matrix[i - 1][j], matrix[i - 1][j + 1]) + matrix[i][j];
                }
                else if (j == n - 1)
                {
                    matrix[i][j] = min(matrix[i - 1][j], matrix[i - 1][j - 1]) + matrix[i][j];
                }
                else
                    matrix[i][j] = min(min(matrix[i - 1][j - 1], matrix[i - 1][j]), matrix[i - 1][j + 1]) + matrix[i][j];
                if (i == n - 1)
                    M = min(M, matrix[i][j]);
            }
        return M;
    }
};