Leetcode.213 打家劫舍 II
题目链接
题目描述
你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都 围成一圈 ，这意味着第一个房屋和最后一个房屋是紧挨着的。同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警 。
给定一个代表每个房屋存放金额的非负整数数组，计算你 在不触动警报装置的情况下 ，今晚能够偷窃到的最高金额。
解法：动态规划
我们定义
f
(
i
,
j
)
f(i,j)
f(i,j) 表示 小偷能从区间
[
i
,
j
]
[i,j]
[i,j] 偷窃的最高金额。
对于第一个房间
n
u
m
s
[
0
]
nums[0]
nums[0]：
- 偷窃第一个房间
n
u
m
s
[
0
]
nums[0]
nums[0]，那么就不能偷n
u
m
s
[
1
]
nums[1]
nums[1] 和n
u
m
s
[
n
−
1
]
nums[n - 1]
nums[n−1]。所以在偷第一个房间n
u
m
s
[
0
]
nums[0]
nums[0] 的情况下，最多能偷n
u
m
s
[
0
]
+
f
(
2
,
n
−
2
)
nums[0] + f(2,n - 2)
nums[0]+f(2,n−2)； - 不偷第一个房间
n
u
m
s
[
0
]
nums[0]
nums[0]，那么最多能偷f
(
1
,
n
−
1
)
f(1,n-1)
f(1,n−1);
我们定义
f
0
f0
f0 为 不偷第
i
i
i 个房间能够偷窃的最高金额；
f
1
f1
f1 为 偷第
i
i
i 个房间能够偷窃的最高金额。
此时，小偷对第
i
+
1
i + 1
i+1 个房间做出选择，偷还是不偷：
-
f
0
′
=
f
1
f0' = f1
f0′=f1； -
n
e
w
_
f
=
m
a
x
(
f
1
,
f
0
+
n
u
m
s
[
i
+
1
]
)
new_f = max(f1 , f0 + nums[i+1])
new_f=max(f1,f0+nums[i+1])； -
f
1
′
=
n
e
w
_
f
f1' = new_f
f1′=new_f；
时间复杂度：
class Solution {
public:
int rob(vector<int>& nums) {
int n = nums.size();
auto fun = [&](int l,int r)->int{
int f0 = 0 , f1 = 0;
for(int i = l;i <= r;i++){
int new_f = max(f1,f0 + nums[i]);
f0 = f1;
f1 = new_f;
}
return f1;
};
return max(nums[0] + fun(2,n - 2) , fun(1,n - 1));
}
};