1289. Minimum Falling Path Sum II

1289. Minimum Falling Path Sum II

Hard

Given an n x n integer matrix grid, return the minimum sum of a falling path with non-zero shifts.

A falling path with non-zero shifts is a choice of exactly one element from each row of grid such that no two elements chosen in adjacent rows are in the same column.

Example 1:

• Input: grid = [[1,2,3],[4,5,6],[7,8,9]]
• Output: 13
• Explanation:

The possible falling paths are:
[1,5,9], [1,5,7], [1,6,7], [1,6,8],
[2,4,8], [2,4,9], [2,6,7], [2,6,8],
[3,4,8], [3,4,9], [3,5,7], [3,5,9]
The falling path with the smallest sum is [1,5,7], so the answer is 13.
```

`
**Example 2:**

- **Input:** grid = [[7]]
- **Output:** 7


**Constraints:**

- `n == grid.length == grid[i].length`
- `1 <= n <= 200`
- `-99 <= grid[i][j] <= 99`

**Solution:**

```
class Solution {

    /**
     * @param Integer[][] $grid
     * @return Integer
     */
    function minFallingPathSum($grid) {
        $n = count($grid);
        $minFirstPathSum = 0;
        $minSecondPathSum = 0;
        $prevMinPathCol = -1;
        $kInfinity = PHP_INT_MAX; 
        foreach ($grid as $row) {
            $newMinFirstPathSum = $kInfinity;
            $newMinSecondPathSum = $kInfinity;
            $newMinPathCol = -1;
            for ($j = 0; $j < $n; ++$j) {
                $currentSum = ($prevMinPathCol != $j ? $minFirstPathSum : $minSecondPathSum) + $row[$j];
                if ($currentSum < $newMinFirstPathSum) {
                    $newMinSecondPathSum = $newMinFirstPathSum;
                    $newMinFirstPathSum = $currentSum;
                    $newMinPathCol = $j;
                } else if ($currentSum < $newMinSecondPathSum) {
                    $newMinSecondPathSum = $currentSum;
                }
            }
            $minFirstPathSum = $newMinFirstPathSum;
            $minSecondPathSum = $newMinSecondPathSum;
            $prevMinPathCol = $newMinPathCol;
        }
        return $minFirstPathSum;
    }
}
```


**Contact Links**

If you found this series helpful, please consider giving the **[repository](https://github.com/mah-shamim/leet-code-in-php)** a star on GitHub or sharing the post on your favorite social networks 😍. Your support would mean a lot to me!

- **[LinkedIn](https://www.linkedin.com/in/arifulhaque/)**
- **[GitHub](https://github.com/mah-shamim)**