Solution
Generally, in questions like these where you have to find the optimal path, your answer is dependent of some future information. Like in this question, to find whether A[0][0] will choose A[1][0] or A[1][1], you need to know what those two will be choosing. So a general approach can be to think it in a bottom-up manner rather than top-down manner. Once we know the path from A[1][0] and A[1][1], A[0][0] will simply be choosing min(A[1][0], A[1][1]).
Start from the second last row and build the path. A[i][j] will choose min({A[i+1][j-1], A[i+1][j], A[i+1][j+1]}). Make sure to handle under/overflow as j-1 can be -1 and j+1 can overflow. Once we have solved for row i, we can similarly solve for row i-1. The answer would be the minimum value in the first row.
int minFallingPathSum(vector<vector<int>>& A) {
int size = A.size();
if (size == 0)
return {0};
int ans = INT_MAX;
for (int i=size-2; i>=0; i--) {
for (int j=0; j<size; j++) {
A[i][j] += min({A[i+1][max(j-1, 0)], A[i+1][j], A[i+1][min(size-1, j+1)]});
}
}
for (int i=0; i<size; i++)
ans = min(ans, A[0][i]);
return ans;
}
Time complexity: O(n^2)
Space complexity: O(1)
Note that it is not a good practice to update the input array so you may use O(n) extra space.