【LeetCode】64.最小路径和

**最小路径和**
================**题目描述**
------------给定一个 `m x n` 的整数矩阵 `grid`,找到从左上角到右下角的最短路径所经过的数字之和。

**示例1:**

输入:`grid = [[1,3,1],[1,5,1],[4,2,1]]`

输出:`7`

解释:因为路径 `1->3->1->-1->1->1` 是从左上角到右下角的最短路径所经过的数字之和。

**示例2:**

输入:`grid = [[1,2,3],[4,5,6]]`

输出:`7`

解释:因为路径 `1->2->4->6` 是从左上角到右下角的最短路径所经过的数字之和。

**限制条件**
------------- `m == grid.length`
- `n == grid[i].length`
- `1 <= m, n <=20`
- `-1000 <= grid[i][j] <=1000`

**解决方案**
------------### 动态规划法我们可以使用动态规划来解决这个问题。动态规划是一种通过分解问题的子问题来求解原问题的方法。

#### 状态定义我们定义一个二维数组 `dp` 来存储从左上角到每个位置的最短路径所经过的数字之和。

- `dp[i][j]`: 表示从左上角到 `(i, j)` 的最短路径所经过的数字之和。

#### 状态转移方程我们可以通过以下状态转移方程来计算 `dp[i][j]`：

- `dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1])`

这个状态转移方程表示从左上角到 `(i, j)` 的最短路径所经过的数字之和等于当前位置的值加上从左上角到 `(i-1, j)` 或 `(i, j-1)` 的最短路径所经过的数字之和中的较小者。

#### 初始化我们需要初始化 `dp` 数组。由于从左上角到左上角的最短路径所经过的数字之和等于当前位置的值，我们可以将 `dp[0][0] = grid[0][0]`。

#### 计算我们可以通过以下循环来计算 `dp[i][j]`：

for i in range(1, m):
 for j in range(1, n):
 dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1])

class Solution:
 def minPathSum(self, grid: List[List[int]]) -> int:
 m, n = len(grid), len(grid[0])
 dp = [[0]*n for _ in range(m)]
 # 初始化 dp[0][0] = grid[0][0]
 # 计算 for i in range(1, m):
 for j in range(1, n):
 dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1])
 return dp[m-1][n-1]

# 状态定义dp = [[0]*n for _ in range(m)] # dp[i][j]: 表示从左上角到 (i, j) 的最短路径所经过的数字之和# 初始化dp[0][0] = grid[0][0] # 从左上角到左上角的最短路径所经过的数字之和等于当前位置的值# 状态转移方程for i in range(1, m):
 for j in range(1, n):
 dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1]) # 从左上角到 (i, j) 的最短路径所经过的数字之和等于当前位置的值加上从左上角到 (i-1, j) 或 (i, j-1) 的最短路径所经过的数字之和中的较小者# 最终答案return dp[m-1][n-1] # 最终答案是 dp[m-1][n-1]