個人主頁：兜里有顆棉花糖
歡迎 點贊?? 收藏? 留言? 加關(guān)注??本文由 兜里有顆棉花糖 原創(chuàng)
收錄于專欄【手撕算法系列專欄】【LeetCode】
??本專欄旨在提高自己算法能力的同時，記錄一下自己的學(xué)習(xí)過程，希望對大家有所幫助
??希望我們一起努力、成長，共同進步。
一、LCR 089. 打家劫舍
點擊可直接跳轉(zhuǎn)到該題目
1??題目描述
一個專業(yè)的小偷，計劃偷竊沿街的房屋。每間房內(nèi)都藏有一定的現(xiàn)金，影響小偷偷竊的唯一制約因素就是相鄰的房屋裝有相互連通的防盜系統(tǒng)，如果兩間相鄰的房屋在同一晚上被小偷闖入，系統(tǒng)會自動報警。
給定一個代表每個房屋存放金額的非負整數(shù)數(shù)組 nums ，請計算 不觸動警報裝置的情況下 ，一夜之內(nèi)能夠偷竊到的最高金額。
示例1：
輸入：nums = [1,2,3,1]
輸出：4
解釋：偷竊 1 號房屋 (金額 = 1) ，然后偷竊 3 號房屋 (金額 = 3)。
偷竊到的最高金額 = 1 + 3 = 4 。
示例2：
輸入：nums = [2,7,9,3,1]
輸出：12
解釋：偷竊 1 號房屋 (金額 = 2), 偷竊 3 號房屋 (金額 = 9)，接著偷竊 5 號房屋 (金額 = 1)。偷竊到的最高金額 = 2 + 9 + 1 = 12 。
注意：
1 <= nums.length <= 1000 <= nums[i] <= 400
2??題目解析
狀態(tài)轉(zhuǎn)移方程如下：
f[i] = g[i - 1] + nums[i-1]g[i] = max(f[i-1],g[i-1])
狀態(tài)表示：
- 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
點擊直接跳轉(zhuǎn)到該題目
1??題目描述
一個專業(yè)的小偷，計劃偷竊一個環(huán)形街道上沿街的房屋，每間房內(nèi)都藏有一定的現(xiàn)金。這個地方所有的房屋都 圍成一圈 ，這意味著第一個房屋和最后一個房屋是緊挨著的。同時，相鄰的房屋裝有相互連通的防盜系統(tǒng)，如果兩間相鄰的房屋在同一晚上被小偷闖入，系統(tǒng)會自動報警。
給定一個代表每個房屋存放金額的非負整數(shù)數(shù)組 nums ，請計算 在不觸動警報裝置的情況下 ，今晚能夠偷竊到的最高金額。
示例1：
輸入：nums = [2,3,2]
輸出：3
解釋：你不能先偷竊 1 號房屋（金額 = 2），然后偷竊 3 號房屋（金額 = 2）, 因為他們是相鄰的。
示例2：
輸入：nums = [1,2,3,1]
輸出：4
解釋：你可以先偷竊 1 號房屋（金額 = 1），然后偷竊 3 號房屋（金額 = 3）。偷竊到的最高金額 = 1 + 3 = 4 。
示例3：
輸入：nums = [0]
輸出：0
注意：
1 <= nums.length <= 1000 <= nums[i] <= 1000
2??題目解析
狀態(tài)表示：
- 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：文章來源：http://www.zghlxwxcb.cn/news/detail-807298.html
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]);
}
};
通過：
文章來源地址http://www.zghlxwxcb.cn/news/detail-807298.html
到了這里，關(guān)于【算法|動態(tài)規(guī)劃No.10】leetcode LCR 089. 打家劫舍 & LCR 090. 打家劫舍 II的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
