64. 最小路径和

         最小路径和问题要求在一个包含非负整数的 m x n 网格中，找到一条从左上角到右下角的路径，使得路径上的数字总和最小。

        与 62. 不同路径 - 力扣（LeetCode）类似，这也是一道典型的动态规划问题。下面我们分析其状态定义和状态转移方程。

状态定义： dp[i][j] 表示从起点 (0,0) 到 (i,j) 的所有路径中的最小数字和。

状态转移方程： 由于只能向右或向下移动，当前状态 dp[i][j] 可以由上方状态 dp[i-1][j] 和左方状态 dp[i][j-1] 转移而来。需要注意两点：

1. 边界处理：第一行只能从左方转移，第一列只能从上方转移，因此需要先初始化这些边界值；
2. 路径和计算：状态转移时需要加上当前网格的数字 grid[i][j]。

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

        代码

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));dp[0][0] = grid[0][0];for (int i = 1;i < m;i++) dp[i][0] = grid[i][0] + dp[i - 1][0];for (int j = 1;j < n;j++) dp[0][j] = grid[0][j] + dp[0][j - 1];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][j];}}return dp[m - 1][n - 1];}
};

        时间复杂度:O(mn),m.n为数组的行，列数

        空间复杂度：O(mn),存储了数组所有位置的状态