931. Minimum Falling Path Sum

Solution

class Solution {
public:
    int minFallingPathSum(vector<vector<int>>& matrix)
    {
        int n = matrix.size();
        if (n == 1) return matrix[0][0];

        int res = INT_MAX;
        for (int i = 1; i < n; i++)
        {
            for (int j = 0; j < n; j++)
            {
                int previous = matrix[i - 1][j];
                if (j > 0)
                {
                    previous = min(previous, matrix[i - 1][j - 1]);
                }
                if (j < n - 1)
                {
                    previous = min(previous, matrix[i - 1][j + 1]);
                }
                matrix[i][j] += previous;
                if (i == n - 1)
                {
                    res = min(res, matrix[i][j]);
                }
            }
        }
        return res;
    }
};

• T:
  $O(N^2)$
• S:
  $O(1)$