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.