题目描述
这是 力扣上的 198. 打家劫舍，难度为 中等。
题目分析
查看咱们给出的题目和示例，我们可以知道，对于偷窃这件事情，咱们不能做，但是题我们还是可以好好实现一波的
偷和不偷是一个问题
对于偷窃最高现金，再加上题目限制咱们不能太贪心，不能偷挨着的两家房屋，那么为了偷到最高现金，自然咱们只有 2 种选择，要么偷单数，要么偷双数，但是我们需要清晰的知道，并不是偷例如序号为 1,3,5,7... ，或者偷 0,2,4,6... 这样是不对的
毕竟对于一个 nums=[2,1,1,2] 的时候，咱们偷的情况其实就是 第 0 个和 第 3 个，也就是并不是全偷单数，或者全偷双数
那么，我们就可以这样来思考了：
对于 nums 长度为 0 的时候，咱们自然返回 0 即可
对于 nuns 长度为 1 的时候，自然返回 nums[0] 即可
对于 nums 长度为 2 的时候，自然是返回 max(nums[0], nums[1]) 即可
但是对于 nums 长度大于 2 的时候，我们需要如何去处理这些数据呢？
面对一个索引为 i 的房间，我们此时如果能获取最大的现金，那么对于我们来说，我们有 2 个选择，投第 i 这间房，或者不偷
如果偷：
相当于目前最高现金是： i-2 前面的房间偷的最高现金 加上 nums[i]
如果不偷：
相当于目前最高现金是：i-1 前面的房间偷的最高现金
此时，咱们使用动态规划，dp 数组来表示，索引 i 对应的房间，目前偷到的最高现金，则有
dp[0] = nums[0]
dp[1] = max(nums[0], nums[1])
dp[2] = max(nums[2] + dp[0] , dp[1])
...
那么，我们就有递推公式：
当i=0,dp[0]=nums[0]当 i = 0, dp[0] = nums[0]当i=0,dp[0]=nums[0]
当i=1,dp[1]=max(nums[0],nums[1])当 i = 1, dp[1] = max(nums[0], nums[1])当i=1,dp[1]=max(nums[0],nums[1])
当i>=2，dp[i]=max(nums[i]+dp[i−2],dp[i−1])当 i >=2，dp[i] = max(nums[i ] + dp[i-2], dp[i-1])当i>=2，dp[i]=max(nums[i]+dp[i−2],dp[i−1])
接下来，咱们就可以来实现编码了，咱们这次使用 golang 的方式来进行实现
Golang 的实现方式：
- 校验 nums 的 0,1,2 的情况
- 对于 nums 的长度为 2 以上的情况下，我们需要去维护好 dp 数组中的数据
- 最后输出 dp[len(nums) - 1] 即可
func rob(nums []int) int { // 对于偷窃现金的，很明确，咱们只能间隔着偷，要么单数，要么双数，此处咱们可以使用动态规划的方式来进行处理 // 因为当前的这个房间能够偷到最高的现金和，有 2 个选择，要么偷，要么不偷，偷当前这一间，那么上一间就不能偷，只能偷上上间 // 当前这间房的最高现金，也是依赖于投上一间或者上上间能够偷到最高现金，因此我们可以使用动态规划的方式来进行处理 // 校验 nums 的长度 n := len(nums) if n == 0{ return 0 }else if n == 1 { return nums[0] }else if n == 2{ return max(nums[0], nums[1]) } // nums 长度大于 2 的情况 dp := make([]int, n) dp[0] = nums[0] dp[1] = max(nums[0], nums[1]) for i:=2; i<n; i++ { dp[i] = max(nums[i]+dp[i-2],dp[i-1]) } return dp[n-1] } func max(a, b int) int { if a>b { return a } return b }
这种实现方式，咱们的时间复杂度是 O(n)，空间复杂度也是 O(n) , 咱们引入了 dp 这个数组来进行存储第 i 个房间能偷到的最大现金，实际上咱们也是可以将空间复杂度降低为 O(1)，感兴趣的，可以评论留言哦
今天就到这里，若有偏差，还请斧正
欢迎点赞，关注，收藏
朋友们，你的支持和鼓励，是我坚持分享，提高质量的动力
好了，本次就到这里
技术是开放的，我们的心态，更应是开放的。拥抱变化，向阳而生，努力向前行。
我是阿兵云原生，欢迎点赞关注收藏，下次见~
