一、LCR 089. 打家劫舍
1️⃣题目描述
一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响小偷偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组 nums ，请计算 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。
2️⃣题目解析
状态转移方程如下：
f[i] = g[i - 1] + nums[i-1]g[i] = max(f[i-1],g[i-1])
状态表示：
- f[i] 表示的是偷取前 i 个房屋中的第 i 个房屋时的最大金额。
- g[i] 表示的是不偷取第 i 个房屋时的最大金额。
3️⃣解题代码
class Solution {
public:
int rob(vector<int>& nums) {
int n = nums.size();
vector<int> f(n + 1);
auto g = f;
for(int i = 1;i <= n;i++)
{
f[i] = g[i - 1] + nums[i-1];
g[i] = max(f[i-1],g[i-1]);
}
return max(f[n],g[n]);
}
};
代码通过啦：
二、LCR 090. 打家劫舍 II
1️⃣题目描述
一个专业的小偷，计划偷窃一个环形街道上沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都 围成一圈 ，这意味着第一个房屋和最后一个房屋是紧挨着的。同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组 nums ，请计算 在不触动警报装置的情况下 ，今晚能够偷窃到的最高金额。
示例1：
示例2：
示例3：
注意：
1 <= nums.length <= 1000 <= nums[i] <= 1000
2️⃣题目解析
状态表示：
- f[i] 表示偷盗i位置时，偷取i位置，此时的最大金额
- g[i] 表示偷盗i位置时，不偷取i位置，此时的最大金额
这里要分两种情况进行讨论：第一种情况是打劫第一家，第二种情况就是不打劫第一家。
情况1（打劫第一家）：最大总金额 = nums[0] + 街道(2,n-2)的最大总金额
情况2（不打劫第一家）：最大总金额 = 街道(1,n-1)的最大总金额
街道(起始位置，终止位置)的最大总金额这里完全按照打家劫舍 I的方式来求取即可。
最终返回值是两种情况的最大值。
3️⃣解题代码
示例代码1：
class Solution {
public:
int rob(vector<int>& nums) {
int n = nums.size();
int ret1 = 0,ret2 = 0;
// 第一种情况:打劫第一家
vector<int> f1(n + 1);
vector<int> g1(n + 1);
for(int i = 3;i <= n-1;i++)
{
f1[i] = nums[i - 1] + g1[i-1];
g1[i] = max(f1[i-1],g1[i-1]);
}
ret1 = max(f1[n-1],g1[n-1]) + nums[0];
// 第二种情况:不打劫第一家
vector<int> f2(n + 1);
vector<int> g2(n + 1);
for(int i = 2;i <= n;i++)
{
f2[i] = nums[i - 1] + g2[i-1];
g2[i] = max(f2[i-1],g2[i-1]);
}
ret2 = max(f2[n],g2[n]);
return max(ret1,ret2);
}
};
示例代码2：
class Solution {
public:
int rob(vector<int>& nums)
{
int n = nums.size();
int ret = max((rob1(nums,2,n-2) + nums[0]),rob1(nums,1,n-1));
return ret;
}
int rob1(vector<int> nums,int l,int r)
{
if(l>r) return 0;
int n = nums.size();
vector<int> f(n);
auto g = f;
f[l] = nums[l];
for(int i = l + 1 ;i <= r;i++)
{
f[i] = nums[i] + g[i-1];
g[i] = max(g[i-1],f[i-1]);
}
return max(f[r],g[r]);
}
};
通过：