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].length1 <= 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 ≠ 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(n3), and the space complexity is O(n2). 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).
PythonJavaC++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)(code-box)
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();
}
}(code-box)
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);
}
};(code-box)
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)
}(code-box)
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);
}(code-box)
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()
}
}(code-box)
