您好，登录后才能下订单哦！
密码登录
登录注册
点击 登录注册 即表示同意《亿速云用户服务条款》
小编给大家分享一下golang刷leetcode动态规划之如何求最小路径和，希望大家阅读完这篇文章之后都有所收获，下面让我们一起去探讨吧！
给定一个包含非负整数的 m x n 网格，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。
说明：每次只能向下或者向右移动一步。
示例:
输入:
[ [1,3,1], [1,5,1], [4,2,1]]
输出: 7
解释: 因为路径 1→3→1→1→1 的总和最小。
解题思路
1,这也是一个典型的动态规划题
2，是递增的
3，状态转移方程为
if step[i-1][j]<step[i][j-1]{ step[i][j]=step[i-1][j]+grid[i][j]}else{ step[i][j]=step[i][j-1]+grid[i][j]}
归纳总结
1，这种矩阵寻找路径类型的题目基本都是动态规划题目
2，动态规划问题都可以递归解，只不过利用空间换时间，存储了最优子结构
3，动态规划主要考察的是问题拆分能力，将一个问题拆分为一个个小问题，然后各个击破。
代码实现
func minPathSum(grid [][]int) int { if len(grid)==0{ return 0 } step:=make([][]int,len(grid)) for i:=0;i<len(grid);i++{ step[i]=make([]int,len(grid[0])) } step[0][0]=grid[0][0] for i:=1;i<len(grid);i++{ step[i][0]=step[i-1][0]+grid[i][0] } for i:=1;i<len(grid[0]);i++{ step[0][i]=step[0][i-1]+grid[0][i] } for i:=1;i<len(grid);i++{ for j:=1;j<len(grid[0]);j++{ if step[i-1][j]<step[i][j-1]{ step[i][j]=step[i-1][j]+grid[i][j] }else{ step[i][j]=step[i][j-1]+grid[i][j] } } } return step[len(grid)-1][len(grid[0])-1]}
看完了这篇文章，相信你对“golang刷leetcode动态规划之如何求最小路径和”有了一定的了解，如果想了解更多相关知识，欢迎关注亿速云行业资讯频道，感谢各位的阅读！
免责声明：本站发布的内容（图片、视频和文字）以原创、转载和分享为主，文章观点不代表本网站立场，如果涉及侵权请联系站长邮箱：is@yisu.com进行举报，并提供相关证据，一经查实，将立刻删除涉嫌侵权内容。