1289. Minimum Falling Path Sum II Hard

1/**
2 * [1289] Minimum Falling Path Sum II
3 *
4 * Given an n x n integer matrix grid, return the minimum sum of a falling path with non-zero shifts.
5 * 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.
6 *  
7 * Example 1:
8 * <img alt="" src="https://assets.leetcode.com/uploads/2021/08/10/falling-grid.jpg" style="width: 244px; height: 245px;" />
9 * Input: arr = [[1,2,3],[4,5,6],[7,8,9]]
10 * Output: 13
11 * Explanation: 
12 * The possible falling paths are:
13 * [1,5,9], [1,5,7], [1,6,7], [1,6,8],
14 * [2,4,8], [2,4,9], [2,6,7], [2,6,8],
15 * [3,4,8], [3,4,9], [3,5,7], [3,5,9]
16 * The falling path with the smallest sum is [1,5,7], so the answer is 13.
17 * 
18 * Example 2:
19 * 
20 * Input: grid = [[7]]
21 * Output: 7
22 * 
23 *  
24 * Constraints:
25 * 
26 * 	n == grid.length == grid[i].length
27 * 	1 <= n <= 200
28 * 	-99 <= grid[i][j] <= 99
29 * 
30 */
31pub struct Solution {}
32
33// problem: https://leetcode.com/problems/minimum-falling-path-sum-ii/
34// discuss: https://leetcode.com/problems/minimum-falling-path-sum-ii/discuss/?currentPage=1&orderBy=most_votes&query=
35
36// submission codes start here
37
38impl Solution {
39    pub fn min_falling_path_sum(grid: Vec<Vec<i32>>) -> i32 {
40        0
41    }
42}
43
44// submission codes end
45
46#[cfg(test)]
47mod tests {
48    use super::*;
49
50    #[test]
51    fn test_1289() {
52    }
53}
54