golang刷leetcode动态规划之如何求最小路径和

小编给大家分享一下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动态规划之如何求最小路径和”有了一定的了解,如果想了解更多相关知识,欢迎关注亿速云行业资讯频道,感谢各位的阅读!

原创文章,作者:506227337,如若转载,请注明出处:https://blog.ytso.com/224012.html

(0)
上一篇 2022年1月7日
下一篇 2022年1月7日

相关推荐

发表回复

登录后才能评论