LeetCode刷题记录 |
- 🌐 我的博客主页:iiiiiankor
- 🎯 如果你觉得我的内容对你有帮助,不妨点个赞👍、留个评论✍,或者收藏⭐,让我们一起进步!
- 📝 专栏系列:LeetCode 刷题日志
- 🌱 文章内容来自我的学习与实践经验,如果你有任何想法或问题,欢迎随时在评论区交流讨论。让我们一起探索更多的可能!🚀
文章目录
- 📜题目描述
- 💡解题思路
- ⌨C++代码
📜题目描述
给定一个包含非负整数的
m x n
网格grid
,请找出一条从左上角到右下角的路径,使得路径上的数字总和为最小。
说明:每次只能向下或者向右移动一步。
示例1
输入:grid = [[1,3,1],[1,5,1],[4,2,1]]
输出:7
解释:因为路径 1→3→1→1→1 的总和最小。
💡解题思路
每一步只能向下走或者向右走
状态定义
dp[i][j]
: 从[0][0]
到[i][j]
位置的最小路径和
[i][j]
可以到达 [i+1][j]
或者 [i][j+1]
[i][j]
可以由[i+1][j]
或者[i][j+1]
到达
状态转移
dp[i][j]=grid[i][j] + min(dp[i-1][j],dp[i][j-1])
特殊情况:
- j==0,
dp[i][j]=grid[i][j] + dp[i-1][j]
- i==0,
dp[i][j]=grid[i][j] + dp[i][j-1]
初始值
dp[0][0] = gird[0][0]
返回结果
遍历二维数组,找到最小值