We read every piece of feedback, and take your input very seriously.
To see all available qualifiers, see our documentation.
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
给定一个包含非负整数的 m x n 网格,请找出一条从左上角到右下角的路径,使得路径上的数字总和为最小。
**说明:**每次只能向下或者向右移动一步。
输入: [ [1,3,1], [1,5,1], [4,2,1] ] 输出: 7 解释: 因为路径 1→3→1→1→1 的总和最小。
来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/minimum-path-sum
这个题一看就是动态规划题,我的思路是,要想到达右下角,有两种方式。 第一种:到达右下角上边的元素 第二种:到达右下角左边的元素 然后对比这两种元素,哪个加起来最小,那就选择哪个,依次类推: 数组只剩下一行:到达最后的元素就是这一行数据相加即可 数组只剩下一列:到达最后的元素就是这一列数据相加即可
func minPathSum(grid [][]int) int { m := map[string]int{} return dp(grid, m) } func dp(grid [][]int, m map[string]int) int { rows, columns := len(grid), len(grid[0]) str := strconv.Itoa(rows) + "*" + strconv.Itoa(columns) if v, e := m[str]; e { return v } if rows == 1 { var ret int for _, v := range grid[0] { ret += v } return ret } if columns == 1 { var ret int for _, v := range grid { ret += v[0] } return ret } top := grid[:rows-1] left := [][]int{} for i := 0; i < rows; i++ { left = append(left, grid[i][:columns-1]) } mix := min(grid[rows-1][columns-1]+dp(top, m), grid[rows-1][columns-1]+dp(left, m)) m[str] = mix return mix } func min(x, y int) int { if x > y { return y } return x }
这个思路应该是最菜的思路了,有时间再来优化一下。
The text was updated successfully, but these errors were encountered:
No branches or pull requests
给定一个包含非负整数的 m x n 网格,请找出一条从左上角到右下角的路径,使得路径上的数字总和为最小。
**说明:**每次只能向下或者向右移动一步。
示例:
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/minimum-path-sum
解答
这个题一看就是动态规划题,我的思路是,要想到达右下角,有两种方式。
第一种:到达右下角上边的元素
第二种:到达右下角左边的元素
然后对比这两种元素,哪个加起来最小,那就选择哪个,依次类推:
数组只剩下一行:到达最后的元素就是这一行数据相加即可
数组只剩下一列:到达最后的元素就是这一列数据相加即可
动态规划 + 递归
这个思路应该是最菜的思路了,有时间再来优化一下。
The text was updated successfully, but these errors were encountered: