题目主要信息:
给定一个数组，其中代表每家拥有的钱数
小偷每次不能偷取数组中相邻位置的钱，只要不相邻的钱都可以偷
数组形成环形，第一家与最后一家相邻
求最多能偷到钱数
举一反三：
学习完本题的思路你可以解决如下题目：
BM78.打家劫舍(一)
BM80.买卖股票的最好时机(一)
BM81.买卖股
展开全文
还是dp，只是相较于没有首末次约束的情况下多了一个思维过程而已。由于不能同时偷首末家，因此一共有三种可能：偷最多的钱要么是1.偷了首家，不偷末家，要么是2.偷了末家，不偷首家，要么是3.首末家都没偷。因此可以做两个dp向量，一个dp不包括首家，一个dp不包括末家，最后返回两者较大者即可。
#
# 代
展开全文
/*
当前家不偷或偷
当前不偷所获最大利润 = max(前一天不偷，前一天偷)；
dp[i][0] = max(dp[i-1][0],dp[i-1][1]);
当前偷所获最大利润 = 前一天没偷 + 今日所得
dp[i]
展开全文
题意整理
给定n个房子排成一圈，每个房子都有一定现金。
现在有一个小偷，想偷到尽可能多的现金，但是不能偷相邻的房间，问最多偷多少现金。
方法一（动态规划）
1.解题思路
状态定义：dp[i]dp[i]dp[i]表示到第i个房间为止，能偷到的最多的现金。
状态初始化：到第0个房间时，最多偷第0个
展开全文
题目主要信息:
给定一个数组，其中代表每家拥有的钱数
小偷每次不能偷取数组中相邻位置的钱，只要不相邻的钱都可以偷
数组形成环形，第一家与最后一家相邻
求最多能偷到钱数
具体思路:
这道题与打家劫舍（一）比较类似，区别在于这道题是环形，第一家和最后一家是相邻的，既然如此，在原先的方案中第一家和最后
展开全文
跟(一)同样的解法，dp定义也完全不用变。跑两遍而已
环形只影响最后一个房子的选择:
- 如果偷了第0个房子，那最后一个房子就偷不了。
- 如果不偷第0个房子，那最后一个房子可以选择偷或着不偷
那岂不是把两个情况都跑一遍 挑个更好的就行了。。。
偷了第0个房子：
在第1个房子时，
g(1
展开全文
首先可以看一下我的打家劫舍(1)的题解
打家劫舍(1)题解链接
回到本题，题目在原有基础上加上了环
分类讨论一下:
1.当要偷第一个房子的时候，能偷到范围是哪些?
相邻的不能偷，最后一个房子不能偷
那么就是
2.当不偷第一个房子时能偷的范围?
排除掉第一个，从第二个房子到最后都可以偷
那么我们
展开全文
动态规划,dp[i] = max(dp[i + 2] + nums[i], dp[i + 1]),由于围城了一个圈,第一家和最后一家算作相邻,即求 nums[1:] 和 nums[:-1] 上的最大 dp 值
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
#
展开全文
到第i家时，最大收益取决于前面一家是否已偷，状态转移为
dp[i]=max(dp[i-1],dp[i-2]+nums[i])
本题区别于打家劫舍（一）的关键要点在于闭环的位置，即第一家和最后一家衔接
可以通过定义2个动态规划数组用来保存第一家偷钱dp1和未偷钱dp2的两种情况，到最后一家时：
如果
展开全文
public int rob (int[] nums) {
if(nums.length == 1)return nums[
展开全文
-
扫描二维码，关注牛客
- 意见反馈
-
下载牛客APP，随时随地刷题
- 牛客竞赛，专业的竞技算法训练平台
-
扫描二维码，进入QQ群
扫码关注“比赛自动姬”
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备 11010502036488号
