提供了编程的基础技术教程

zl程序教程

您现在的位置是：首页 >  其他

当前栏目

golang刷leetcode：BM79 打家劫舍(二)

2023-02-18 16:32:26 时间

描述

你是一个经验丰富的小偷，准备偷沿湖的一排房间，每个房间都存有一定的现金，为了防止被发现，你不能偷相邻的两家，即，如果偷了第一家，就不能再偷第二家，如果偷了第二家，那么就不能偷第一家和第三家。沿湖的房间组成一个闭合的圆形，即第一个房间和最后一个房间视为相邻。

给定一个长度为n的整数数组nums，数组中的元素表示每个房间存有的现金数额，请你计算在不被发现的前提下最多的偷窃金额。

示例1

输入：

[1,2,3,4]

复制

返回值：

6

复制

说明：

最优方案是偷第 2 4 个房间

示例2

输入：

[1,3,6]

复制

返回值：

6

复制

说明：

由于 1 和 3 是相邻的，因此最优方案是偷第 3 个房间

解题思路：

1，本题是个环形的，所以比较难处理

2，其实可以拆成两个子问题

A，抢劫第一家，不抢劫最后一家

B，抢劫最后一家，不抢劫第一家

3，拆成这两个子问题后，剩余的就是简单的第一种情况了,状态转移方程为：

dp[i]=max(dp[i-1],dp[i-2]+nums[i])

4,依赖两个值，可以降维度优化

代码实现： 

package main

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param nums int整型一维数组 
 * @return int整型
*/
func rob( nums []int ) int {
    // write code here
    switch len(nums){
        case 0:
         return 0
        case 1:
         return nums[1]
        case 2:
        if nums[0]>nums[1]{
            return nums[0]
        }
        return nums[1]
        default:
    }
    dp:=[2]int{nums[0],nums[1]}
    if nums[0]>nums[1]{
        dp[1]=nums[0]
    }
    start:=getDp(nums,dp,len(nums)-1)
    end:=getDp(nums,[2]int{0,nums[1]},len(nums))
    if start<end{
        return end
    }
    return start
}

func getDp(nums []int,dp [2]int ,end int)int{
        for i:=2;i<end;i++{
        tmp:=dp[1]
        if dp[0]+nums[i]>dp[1]{
            dp[1]=dp[0]+nums[i]
        }
        dp[0]=tmp
    }
    return dp[1]
}

相关文章