931. Minimum Falling Path Sum

Given a square array of integers A, we want the minimum sum of a falling path through A.

A falling path starts at any element in the first row, and chooses one element from each row. The next row's choice must be in a column that is different from the previous row's column by at most one.

Example 1:

Input: [[1,2,3],[4,5,6],[7,8,9]]
Output: 12
Explanation: 
The possible falling paths are:

• [1,4,7], [1,4,8], [1,5,7], [1,5,8], [1,5,9]

• [2,4,7], [2,4,8], [2,5,7], [2,5,8], [2,5,9], [2,6,8], [2,6,9]

• [3,5,7], [3,5,8], [3,5,9], [3,6,8], [3,6,9]

The falling path with the smallest sum is [1,4,7], so the answer is 12.

利用一個1D dp array儲存前一排的結果，dp state transition: dp[i][j] = min({dp[i - 1][j - 1], dp[i - 1][j], dp[i - 1][j + 1]}) + A[i][j]

// Dynamic Programming
int minFallingPathSum(vector<vector<int>>& A) { // time: O(m * n); space: O(n)
    int m = A.size(), n = A[0].size();
    vector<int> dp(A[0].begin(), A[0].end());
    for (int i = 1; i < m; ++i) {
        vector<int> t(n, 0);
        for (int j = 0; j < n; ++j) {
            t[j] = min({dp[max(0, j - 1)], dp[j], dp[min(n - 1, j + 1)]}) + A[i][j];
        }
        dp = t;
    }
    return *min_element(dp.begin(), dp.end());
}