Leetcode 931. Minimum Falling Path Sum

Problem Link: https://leetcode.com/problems/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. 1 <= A.length == A[0].length <= 100
2. -100 <= A[i][j] <= 100

Solution:

We are given a square grid of size n * n.

What we want is the minimum falling path sum. ie. the minimum sum while falling through row 0 to row (n - 1)

The constraints in the problem is while falling from column of ith row to (i + 1)th row, we can fall on either of the columns {j - 1, j , j+ 1} as it is mentioned that the choice of next row must be in a column that is different from the previous row's column by at most one.


Similar to other grid dp problems, I'm gonna start with the case when I'm at (i, j) cell. How can I reach (i, j) cell??
We can reach (i, j) cell from either of (i - 1, j - 1), (i - 1, j) or (i - 1, j - 1) cell.


Let dp[i][j] gives the minimum possible falling path sum. Then

 dp[i][j] = A[i][j] + min(dp[i - 1][j - 1], dp[i - 1][j], dp[i - 1][j - 1]) 

We must consider a special case for the first row(0th). There is no way to fall to 0th row so, minimum falling path cost is given by the weight of the cell itself

 dp[0][i] = A[0][i] 

Now we are almost done with the solution , for every cell(i, j) form(1, 0) to (n - 1, n- 1) we fill up the dp table in bottom up manner. See the implementation .

Implementation: 

class Solution {
public:
    int minFallingPathSum(vector<vector<int>>& A) {
        
        // Size of grid
        int n = A.size();
        
        // dp[i][j] gives the minimum sum of falling path for cell(i, j)
        vector<vector<int>> dp(n, vector<int> (n, INT_MAX));
        
        // For cell at 0th row we can't fall from any row
        // So for all cells at 0th row minimum sum of falling is the
        // value of eleement itself
        for(int i = 0; i < n; i++){
            dp[0][i] = A[0][i];
        }
        
        
        // Suppose our ans is infinite
        int ans = INT_MAX;
        
        // For all rows from 1 to n - 1
        // We can fall to cell (i, j) from (i - 1, j - 1) or (i - 1, j) or (i - 1, j          + 1)
        
        for(int i  = 1; i < n; i++){
            for(int j = 0; j < n; j++){
                
                // if cell(i, j) is not of last column
                // we can fall from previous row (i - 1, j + 1) with
                //  column greater than 1
                if(j + 1 < n){
                   dp[i][j] =   min(dp[i][j], dp[i - 1][j + 1]);
                }
                // if cell(i, j) is not of first column
                // we can fall from previous row (i - 1, j - 1) with
                //  column less than 1
                if(j - 1 >= 0){
                     dp[i][j] =  min(dp[i][j], dp[i - 1][j - 1]);
                }
                
                // Otherwise we can fall directly from the cell above it(i - 1, j -                 1)
                dp[i][j] =  min(dp[i][j] , dp[i - 1][j]);
                
                // Cost of falling is minimum of the paths and current value of the cell (i, j)
                dp[i][j] += A[i][j];
                
            }
        }
        
        
        // Loop through all elements at last row and compute the minimum value
        // which is the minimum sum of a falling path
        for(auto x: dp[n - 1]){
            ans = min(ans, x);
        }
        return ans;
    }  
};