The Dynamic Programming Algorithm to Compute the 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.

Note:
1 <= A.length == A[0].length <= 100
-100 <= A[i][j] <= 100

Dynamic Programming Algorithm to Compute the Minimal Path Sum

If we are at (row, col), we can fall into three possible locations, (row + 1, col – 1), (row + 1, col) and (row + 1, col + 1). We can update the array elements as to simulate the falling process – the accumulated min sum. Each element will be the minimal of the three (or less) possible locations it could fall from.

The DP process could be from top-down, or in the reverse bottom-up, which doewsn’t matter. The DP formula is as follows.

DP(i, j) = min(DP(i - 1, j - 1), DP(i - 1, j), DP(i - 1, j + 1)) + A[i, j]
DP(i, j) = 0 if i < 0 or j >= C where C is the max column
Answer is Min(DP(row - 1))

You can use this algorithm to find minimal path sum in any shape of matrix, for example, a triangle. The following C++ code implements the Dynamic Programming algorithm to find the minimal path sum of a matrix, which runs at O(N) where N is the number of elements in the matrix. The constant space is used, as we directly modify the array elements for intermdiate (accumulated) minimal path sum along the way.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

class Solution {
public:
    int minFallingPathSum(vector<vector<int>>& A) {
        int row = A.size(), col = A[0].size();
        for (int i = 1; i < row; ++ i) {
            for (int j = 0; j < col; ++ j) {
                int v = A[i - 1][j];
                if (j > 0) {
                    v = min(v, A[i - 1][j - 1]);
                }
                if (j + 1 < col) {
                    v = min(v, A[i - 1][j + 1]);
                }
                A[i][j] += v; // updated the accumulated min path sum
            }
        }
        // find minimal of the last row
        return *min_element(A[row - 1].begin(), A[row - 1].end());
    }
};

class Solution {
public:
    int minFallingPathSum(vector<vector<int>>& A) {
        int row = A.size(), col = A[0].size();
        for (int i = 1; i < row; ++ i) {
            for (int j = 0; j < col; ++ j) {
                int v = A[i - 1][j];
                if (j > 0) {
                    v = min(v, A[i - 1][j - 1]);
                }
                if (j + 1 < col) {
                    v = min(v, A[i - 1][j + 1]);
                }
                A[i][j] += v; // updated the accumulated min path sum
            }
        }
        // find minimal of the last row
        return *min_element(A[row - 1].begin(), A[row - 1].end());
    }
};

We need to find the minimal path sum in the last row, using a for-loop or the *min_element in Modern C++.

–EOF (The Ultimate Computing & Technology Blog) —