1289. Minimum Falling Path Sum II

Description

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

Solutions

Solution 1: Dynamic Programming

We define \(f[i][j]\) to represent the minimum sum of the first \(i\) rows, with the last number in the \(j\)-th column. The state transition equation is:

\[ f[i][j] = \min_{k \neq j} f[i - 1][k] + grid[i - 1][j] \]

where \(k\) represents the column of the number in the \((i - 1)\)-th row, and the number in the \(i\)-th row and \(j\)-th column is \(grid[i - 1][j]\).

The final answer is the minimum value in \(f[n]\).

The time complexity is \(O(n^3)\), and the space complexity is \(O(n^2)\). Here, \(n\) is the number of rows in the matrix.

We note that the state \(f[i][j]\) only depends on \(f[i - 1][k]\), so we can use a rolling array to optimize the space complexity to \(O(n)\).

Python3JavaC++GoTypeScriptRust

class Solution:
    def minFallingPathSum(self, grid: List[List[int]]) -> int:
        n = len(grid)
        f = [0] * n
        for row in grid:
            g = row[:]
            for i in range(n):
                g[i] += min((f[j] for j in range(n) if j != i), default=0)
            f = g
        return min(f)

class Solution {
    public int minFallingPathSum(int[][] grid) {
        int n = grid.length;
        int[] f = new int[n];
        final int inf = 1 << 30;
        for (int[] row : grid) {
            int[] g = row.clone();
            for (int i = 0; i < n; ++i) {
                int t = inf;
                for (int j = 0; j < n; ++j) {
                    if (j != i) {
                        t = Math.min(t, f[j]);
                    }
                }
                g[i] += (t == inf ? 0 : t);
            }
            f = g;
        }
        return Arrays.stream(f).min().getAsInt();
    }
}

class Solution {
public:
    int minFallingPathSum(vector<vector<int>>& grid) {
        int n = grid.size();
        vector<int> f(n);
        const int inf = 1e9;
        for (const auto& row : grid) {
            vector<int> g = row;
            for (int i = 0; i < n; ++i) {
                int t = inf;
                for (int j = 0; j < n; ++j) {
                    if (j != i) {
                        t = min(t, f[j]);
                    }
                }
                g[i] += (t == inf ? 0 : t);
            }
            f = move(g);
        }
        return ranges::min(f);
    }
};

func minFallingPathSum(grid [][]int) int {
    f := make([]int, len(grid))
    const inf = math.MaxInt32
    for _, row := range grid {
        g := slices.Clone(row)
        for i := range f {
            t := inf
            for j := range row {
                if j != i {
                    t = min(t, f[j])
                }
            }
            if t != inf {
                g[i] += t
            }
        }
        f = g
    }
    return slices.Min(f)
}

function minFallingPathSum(grid: number[][]): number {
    const n = grid.length;
    const f: number[] = Array(n).fill(0);
    for (const row of grid) {
        const g = [...row];
        for (let i = 0; i < n; ++i) {
            let t = Infinity;
            for (let j = 0; j < n; ++j) {
                if (j !== i) {
                    t = Math.min(t, f[j]);
                }
            }
            g[i] += t === Infinity ? 0 : t;
        }
        f.splice(0, n, ...g);
    }
    return Math.min(...f);
}

impl Solution {
    pub fn min_falling_path_sum(grid: Vec<Vec<i32>>) -> i32 {
        let n = grid.len();
        let mut f = vec![0; n];
        let inf = i32::MAX;

        for row in grid {
            let mut g = row.clone();
            for i in 0..n {
                let mut t = inf;
                for j in 0..n {
                    if j != i {
                        t = t.min(f[j]);
                    }
                }
                g[i] += if t == inf { 0 } else { t };
            }
            f = g;
        }

        *f.iter().min().unwrap()
    }
}

1289. Minimum Falling Path Sum II

Description

Solutions

Solution 1: Dynamic Programming

Comments