Minimum Path Sum

64. 最小路径和

分析

状态定义：
- 用 f[i][j] 表示从起点 (0, 0) 到达位置 (i, j) 的路径数字总和的最小值
状态转移：
- 如果机器人可以从上方或左方到达 (i, j)，则：f[i][j] = min(f[i-1][j], f[i][j-1]) + grid[i][j]
- 边界情况：
  - 如果位于第一行，则只能从左侧到达：f[0][j] = f[0][j-1] + grid[0][j]
  - 如果位于第一列，则只能从上方到达：f[i][0] = f[i-1][0] + grid[i][0]
初始条件：
- 起点 (0, 0) 的路径和等于网格的初始值：f[0][0] = grid[0][0]

时间复杂度

动态规划遍历整个网格，每个位置只需计算一次，时间复杂度为 O(mn)

空间复杂度

空间复杂度为 O(mn)

C++代码

 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


class Solution
{
public:
    int minPathSum(vector<vector<int>>& grid)
    {
        // 获取网格的行数和列数
        int n = grid.size();
        if (n == 0)
            return 0; // 如果网格为空，直接返回 0
        int m = grid[0].size();

        // 初始化动态规划数组，所有值初始为 INT_MAX
        std::vector<std::vector<int>> f(n, std::vector<int>(m, INT_MAX));

        // 动态规划计算每个位置的最小路径和
        for (int i = 0; i < n; ++i)
        {
            for (int j = 0; j < m; ++j)
            {
                if (i == 0 && j == 0)
                    // 起点
                    f[i][j] = grid[i][j];
                else
                {
                    // 从上方到达
                    if (i)
                        f[i][j] = std::min(f[i][j], f[i - 1][j] + grid[i][j]);
                    // 从左方到达
                    if (j)
                        f[i][j] = std::min(f[i][j], f[i][j - 1] + grid[i][j]);
                }
            }
        }

        // 返回右下角的最小路径和
        return f[n - 1][m - 1];
    }
};