【golang】leetcode初级-最大子序和&打家劫舍【golang】leetcode初级-最大子序

什么是动态规划 https://zhuanlan.zhihu.com/p/...
第一题最大子序和题目信息

文章图片

解题思路

文章图片

文章图片

一开始在思考的时候走错了方向

文章图片

直到看到这条评论得到了启发
错误代码如下

文章图片

正确代码如下

func maxSubArray(nums []int) int { max := nums[0] for i := 1; i < len(nums); i++ { if nums[i] + nums[i-1] > nums[i] { nums[i] += nums[i-1] } if nums[i] > max { max = nums[i] } } return max }

第二题打家劫舍题目信息

文章图片

解题思路
【【golang】leetcode初级-最大子序和&打家劫舍】同样为多决策问题，动态规划可以快速的解决

文章图片

代码

func rob(nums []int) int { if len(nums) == 0 { return 0 } if len(nums) == 1 { return nums[0] } dp := make([]int, len(nums)) dp[0] = nums[0] dp[1] = max(nums[0], nums[1]) for i := 2; i < len(nums); i++ { dp[i] = max(dp[i-2] + nums[i], dp[i-1]) } return dp[len(nums)-1] }func max(x, y int) int { if x > y { return x } return y }作者：LeetCode-Solution 链接：https://leetcode-cn.com/problems/house-robber/solution/da-jia-jie-she-by-leetcode-solution/ 来源：力扣（LeetCode）著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。