【Leetcode每日一题】动态规划 - 最小路径和（难度⭐⭐）（58）

1. 题目解析

题目链接：64. 最小路径和

这个问题的理解其实相当简单，只需看一下示例，基本就能明白其含义了。

2.算法原理

算法思路梳理：

一、状态表示

在路径类问题中，状态表示通常有两种形式：

从 [i, j] 位置出发，进行某种操作后的状态；
从起始位置出发，到达 [i, j] 位置的状态。

在这里，我们选择第二种方式来定义状态：dp[i][j] 表示到达 [i, j] 位置时的最小路径和。

二、状态转移

考虑到达 [i, j] 位置的最小路径和，根据问题的性质，我们可以知道这个最小路径和是由其上方的位置 [i-1, j] 或左方的位置 [i, j-1] 转移而来。因此，我们需要取这两种情况下的最小值，并加上当前位置 [i, j] 的值。

具体状态转移方程为：dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]

这里，grid[i][j] 表示表格中位置 [i, j] 的值。

三、初始化

为了正确地进行动态规划填表，我们需要对状态数组 dp 进行初始化。一种常见的技巧是在表格的最上方和最左侧添加辅助结点。这些辅助结点的值需要保证后续填表过程的正确性。

在本题中，我们可以在表格的上方和左侧各添加一行一列，并将这些位置的值初始化为正无穷大（表示不可达状态）。然后，将 dp[0][1] 和 dp[1][0] 设置为起始位置的值（通常为1），作为路径的起点。

四、填表顺序

根据状态转移方程，我们可以确定填表的顺序。由于每个位置的状态是由其上方和左方位置的状态转移而来，因此我们需要按照“从上往下”的顺序填充每一行，而在填充每一行时，又需要按照“从左往右”的顺序进行。

五、返回值

根据状态表示的定义，最终我们需要返回的是到达表格右下角位置 [m, n] 时的最小路径和，即 dp[m][n]。

3.代码编写

class Solution 
{
public:
    int minPathSum(vector<vector<int>>& grid) 
    {
        int m = grid.size(), n = grid[0].size();
        vector<vector<int>> dp(m + 1, vector<int>(n + 1, INT_MAX));
        dp[0][1] = dp[1][0] = 0;
        for(int i = 1; i <= m; i++)
        {
            for(int j = 1; j <= n; j++)
            {
                dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + grid[i - 1][j - 1];
            }
        }
        return dp[m][n];
    }
};