## 1289. Minimum Falling Path Sum II

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

Return the minimum sum of a falling path with non-zero shifts.

Example 1:

Input: arr = [[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.

Constraints:

• 1 <= arr.length == arr[i].length <= 200
• -99 <= arr[i][j] <= 99

## Rust Solution

struct Solution;

impl Solution {
fn min_falling_path_sum(arr: Vec<Vec<i32>>) -> i32 {
let n = arr.len();
let m = arr[0].len();
let mut dp = vec![vec![0; m]; n + 1];
for i in 0..n {
for j in 0..m {
let mut min = std::i32::MAX;
for k in 0..m {
if k != j {
min = min.min(dp[i][k]);
}
}
dp[i + 1][j] = arr[i][j] + min;
}
}
*dp[n].iter().min().unwrap()
}
}

#[test]
fn test() {
let arr = vec_vec_i32![[1, 2, 3], [4, 5, 6], [7, 8, 9]];
let res = 13;
assert_eq!(Solution::min_falling_path_sum(arr), res);
}

Having problems with this solution? Click here to submit an issue on github.