求解矩阵最小路径和问题
时间: 2024-05-13 14:17:20 浏览: 6
矩阵最小路径和问题可以使用动态规划来解决。假设矩阵为 $M$,$M_{i,j}$ 表示第 $i$ 行、第 $j$ 列的元素值,我们可以定义一个新的矩阵 $dp$,其中 $dp_{i,j}$ 表示从左上角 $(1,1)$ 到 $(i,j)$ 的最小路径和。则有以下状态转移方程:
$$
dp_{i,j} = \begin{cases}
M_{i,j} & i=1 \text{且} j=1 \\
dp_{i,j-1}+M_{i,j} & i=1 \text{且} j>1 \\
dp_{i-1,j}+M_{i,j} & i>1 \text{且} j=1 \\
\min(dp_{i,j-1}, dp_{i-1,j})+M_{i,j} & i>1 \text{且} j>1
\end{cases}
$$
最终的最小路径和为 $dp_{m,n}$,其中 $m$ 是矩阵的行数,$n$ 是矩阵的列数。
下面是一个 Python 代码实现:
```python
def min_path_sum(matrix):
m, n = len(matrix), len(matrix[0])
dp = [[0] * n for _ in range(m)]
dp[0][0] = matrix[0][0]
for i in range(1, m):
dp[i][0] = dp[i-1][0] + matrix[i][0]
for j in range(1, n):
dp[0][j] = dp[0][j-1] + matrix[0][j]
for i in range(1, m):
for j in range(1, n):
dp[i][j] = min(dp[i][j-1], dp[i-1][j]) + matrix[i][j]
return dp[m-1][n-1]
```
该函数的参数 `matrix` 是一个二维数组,表示输入的矩阵。函数返回值为矩阵的最小路径和。