潍坊企业网站模板,定制科技软件,wordpress亲子模板,新浪网页打不开题目
给定一个包含非负整数的 m x n 网格 grid #xff0c;请找出一条从左上角到右下角的路径#xff0c;使得路径上的数字总和为最小。 说明#xff1a;每次只能向下或者向右移动一步。
示例
输入#xff1a;grid [[1,3,1],[1,5,1],[4,2,1]] 输出#xff1a;7 解释请找出一条从左上角到右下角的路径使得路径上的数字总和为最小。 说明每次只能向下或者向右移动一步。
示例
输入grid [[1,3,1],[1,5,1],[4,2,1]] 输出7 解释因为路径 1→3→1→1→1 的总和最小。
解析
这道题现在看来会相对简单一些使用动规五部曲直接分析一下就行 1.dp数组及其含义 dp[i][j]表示走到grid[i][j]的时候最小路径和为dp[i][j] 2.递推公式 题目中说了只能向下或者向右那么就是dp[i][j] min(dp[i-1][j], dp[i][j-1]) grid[i][j] 3.初始化 除了dp[0][0]需要初始化之外第一行和第一列也需要初始化
func minPathSum(grid [][]int) int {if len(grid) 0 || len(grid[0]) 0 {return 0}m : len(grid)n : len(grid[0])dp : make([][]int, m1)for i : 0; i m; i {dp[i] make([]int, n1)}dp[0][0] grid[0][0]for i : 1; i m; i { // 第一行初始化dp[i][0] dp[i-1][0] grid[i][0]}for j : 1; j n; j { // 第一列初始化dp[0][j] dp[0][j-1] grid[0][j]}for i : 1; i m; i {for j : 1; j n; j {dp[i][j] min(dp[i-1][j], dp[i][j-1]) grid[i][j] // 递推公式}}return dp[m-1][n-1]
}func min(a, b int) int {if a b {return b}return a
}
