给定一个包含非负整数的mxn网格c
时间: 2024-01-19 16:03:32 浏览: 36
,请找出一条从左上角到右下角的路径,使得路径上的数字总和最小。你每次只能向下或向右移动一步。
可以使用动态规划来解决这个问题。设dp[i][j]为到达第i行第j列时的最小路径和,则有状态转移方程:
dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + c[i][j]
其中,dp[0][0] = c[0][0],dp[0][j] = dp[0][j-1] + c[0][j],dp[i][0] = dp[i-1][0] + c[i][0]。
最终答案为dp[m-1][n-1]。
以下是一个Python代码实现:
```python
def minPathSum(grid):
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):
dp[i][0] = dp[i-1][0] + grid[i][0]
for j in range(1, n):
dp[0][j] = dp[0][j-1] + grid[0][j]
for i in range(1, m):
for j in range(1, n):
dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]
return dp[m-1][n-1]
```
例如,对于输入的网格c:
[
[1,3,1],
[1,5,1],
[4,2,1]
]
最小路径和为7(1->3->1->1->1)。
相关推荐
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)