LeetCode每日一题(931. Minimum Falling Path Sum)

Given an n x n array of integers matrix, return the minimum sum of any falling path through matrix.

A falling path starts at any element in the first row and chooses the element in the next row that is either directly below or diagonally left/right. Specifically, the next element from position (row, col) will be (row + 1, col - 1), (row + 1, col), or (row + 1, col + 1).

Example 1:

Input: matrix = [[2,1,3],[6,5,4],[7,8,9]]
Output: 13

Explanation: There are two falling paths with a minimum sum as shown.

Example 2:

Input: matrix = [[-19,57],[-40,-5]]
Output: -59

Explanation: The falling path with a minimum sum is shown.

Constraints:

• n == matrix.length == matrix[i].length
• 1 <= n <= 100
• -100 <= matrix[i][j] <= 100

---

dp[row][col]是经过 matrix[row][col]这点所能拿到的最小分数， 那就可以推导出 dp[row][col] = min(dp[row+1][col-1], dp[row][col], dp[row][col+1]), 因为我们可以从第一行里面任选一个元素开始下降， 所以 ans = min(dp[0][0], dp[0][1], …, dp[0]matrix[0].length - 1])

---

use std::collections::HashMap;

impl Solution {
    fn dp(
        matrix: &Vec<Vec<i32>>,
        row: usize,
        col: usize,
        cache: &mut HashMap<(usize, usize), i32>,
    ) -> i32 {
        if row == matrix.len() - 1 {
            return matrix[row][col];
        }
        let left = if col > 0 {
            if let Some(c) = cache.get(&(row + 1, col - 1)) {
                *c
            } else {
                Solution::dp(matrix, row + 1, col - 1, cache)
            }
        } else {
            i32::MAX
        };
        let right = if col < matrix[0].len() - 1 {
            if let Some(c) = cache.get(&(row + 1, col + 1)) {
                *c
            } else {
                Solution::dp(matrix, row + 1, col + 1, cache)
            }
        } else {
            i32::MAX
        };
        let bottom = if row < matrix.len() - 1 {
            if let Some(c) = cache.get(&(row + 1, col)) {
                *c
            } else {
                Solution::dp(matrix, row + 1, col, cache)
            }
        } else {
            i32::MAX
        };
        let ans = left.min(right).min(bottom) + matrix[row][col];
        cache.insert((row, col), ans);
        ans
    }

    pub fn min_falling_path_sum(matrix: Vec<Vec<i32>>) -> i32 {
        let mut cache = HashMap::new();
        let mut ans = i32::MAX;
        for col in 0..matrix[0].len() {
            ans = ans.min(Solution::dp(&matrix, 0, col, &mut cache))
        }
        ans
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54