Задача: Сумма вдоль столбцов

Условие: дается квадратная матрица, необходимо вычислить минимальную сумму вдоль столбца.

Есть условие на движение вдоль столбца есть ограничение: можно перемещаться на ячейку вниз лишь по диагонали или строго вниз.

Пример:

Ввод: matrix = [[2,1,3],[6,5,4],[7,8,9]]

Вывод: 13

Объяснение: *во вложении

Решение:

Сложности:

• Временная сложность: O(n2)
• Пространственная сложность: O(n2)

Код:

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