1
2
3
4
5
6
7
8

输入:
[
  [1,3,1],
  [1,5,1],
  [4,2,1]
]
输出: 7
解释: 因为路径 1→3→1→1→1 的总和最小。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

struct Solution;

// @lc code=start
impl Solution {
    /// ## 解题思路
    /// - 动态规划
    /// 1. 设dp[m][n]: mxn网格最小路径和;
    /// 2. 递推公式: dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]
    /// 3. 初始条件: dp[0][0] = grid[0][0];
    pub fn min_path_sum(grid: Vec<Vec<i32>>) -> i32 {
        let (m, n) = (grid.len(), grid[0].len());
        let mut dp = vec![vec![std::i32::MAX; n + 1]; m + 1];
        dp[1][0] = 0;
        dp[0][1] = 0;
        for i in 0..m {
            for j in 0..n {
                dp[i + 1][j + 1] = std::cmp::min(dp[i][j + 1], dp[i + 1][j]) + grid[i][j];
            }
        }

        dp[m][n]
    }
}
// @lc code=end