共计 704 个字符,预计需要花费 2 分钟才能阅读完成。
什么是动静布局
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
}
第二题 打家劫舍
题目信息
解题思路
同样为多决策问题,动静布局能够疾速的解决
代码
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)著作权归作者所有。商业转载请分割作者取得受权,非商业转载请注明出处。
正文完
发表至: Leetcode个人解题总结
2022-01-31