前言
打家劫舍系列
198. 打家劫舍
1_動(dòng)態(tài)規(guī)劃
返回最大金額
不能同時(shí)取相鄰兩個(gè)數(shù)
數(shù)組數(shù)據(jù)全部非負(fù)
①dp數(shù)組含義
dp[i]表示前i個(gè)數(shù)中按規(guī)則取出的最大總和
②遞推公式
dp[i]=max(dp[i-1],dp[i-2]+nums[i])
當(dāng)前最優(yōu)可以從兩個(gè)狀態(tài)推出（前提是前面已經(jīng)為最優(yōu)解）：
1° 前一個(gè)數(shù)未?。簞t當(dāng)前數(shù)取了，則總和最大
2° 前一個(gè)數(shù)已?。罕容^不考慮當(dāng)前數(shù)字的最大總和 （dp[i] ） 以及不考慮上一個(gè)數(shù)字的最大總和加上當(dāng)前數(shù)字（dp[i-2]+nums[i]：因?yàn)楫?dāng)上一個(gè)數(shù)字未取時(shí)，才可以取當(dāng)前數(shù)字）
③dp數(shù)組初始化
因?yàn)檫f推公式中用到了i-2項(xiàng)
所以遍歷時(shí)要從dp數(shù)組的第2項(xiàng)開(kāi)始遍歷，防止數(shù)組越界
所以要初始化dp數(shù)組第2項(xiàng)前面的所有項(xiàng)dp[0]和dp[1]可以手推出來(lái)0&nums[0]
④遍歷順序
當(dāng)前最優(yōu)由已知最優(yōu)推出，應(yīng)正序遍歷
完整代碼：文章來(lái)源：http://www.zghlxwxcb.cn/news/detail-773622.html
int rob(vector<int>& nums) {
// 定義dp數(shù)組&初始化為0
// dp數(shù)組含義：在前i個(gè)數(shù)中按規(guī)則選擇后的最大和
vector<int> dp(nums.size() + 1, 0);
// 因?yàn)檫f推公式會(huì)用到i-2，為保證不越界，初始化到1，并從2開(kāi)始遍歷
// dp[0]沒(méi)有可選的數(shù)字---0
dp[0] = 0;
// dp[1]選上唯一一個(gè)數(shù)則為最大---nums[0]
dp[1] = nums[0];
// 遍歷dp數(shù)組
for (int i = 2; i < dp.size(); i++)
dp[i] = max(dp[i - 1], dp[i - 2] + nums[i-1]);
// 返回答案
return dp[nums.size()];
}
2_優(yōu)化空間復(fù)雜度
由遞推公式可以看出來(lái)，當(dāng)前項(xiàng)只需要用到前兩項(xiàng)就可以推出
所以：
不用將dp數(shù)組長(zhǎng)度開(kāi)為nums數(shù)組的長(zhǎng)度
用兩個(gè)變量記錄前兩項(xiàng)的值
在遍歷時(shí)更新
// 兩個(gè)變量記錄
// dp[i-2]
int ppre = 0;
// dp[i-1]
int pre = nums[0];
// dp[i]---初始化為nums[0]，當(dāng)nums長(zhǎng)度為1時(shí)范圍首項(xiàng)
int cur = nums[0];
// 遍歷nums數(shù)組
for (int i = 2; i <= nums.size();i++) {
cur = max(pre, ppre + nums[i-1]);
ppre = pre;
pre = cur;
}
// 返回答案
return cur;
213. 打家劫舍 II
1_動(dòng)態(tài)規(guī)劃
在打家劫舍Ⅰ的基礎(chǔ)上加上了條件：
當(dāng)?shù)谝婚g房子被偷過(guò)時(shí)，最后一間房子就不能偷
只有第一間房子，沒(méi)被偷過(guò)時(shí)，最后一間房子才能偷
分（含頭不含尾&含尾不含頭）兩段區(qū)間分別計(jì)算各自的最大值
動(dòng)規(guī)五部曲和打家劫舍Ⅰ大致相同
需要注意：
①
int rob(vector<int>& nums) {
// nums數(shù)組長(zhǎng)度為1時(shí)返回第一項(xiàng)
if (nums.size() == 1)
return nums[0];
// 定義dp數(shù)組
vector<int> dp(nums.size());
// 包含首索引---------------------
// 初始化0，1項(xiàng)
dp[0] = 0;
dp[1] = nums[0];
for (int i = 2; i < dp.size(); i++)
dp[i] = max(dp[i - 1], dp[i - 2] + nums[i - 1]);
int m1 = dp[dp.size() - 1];
// 包含尾索引----------------------
// 初始化1項(xiàng)為2項(xiàng)（間接刪除首索引）
dp[1] = nums[1];
for (int i = 2; i < dp.size(); i++)
dp[i] = max(dp[i - 1], dp[i - 2] + nums[i]);
return max(m1, dp[dp.size() - 1]);
}
2_優(yōu)化空間復(fù)雜度
int rob(vector<int>& nums) {
// 變量記錄法
if (nums.size() == 1)
return nums[0];
// 含頭不含尾----------------------
// dp[i-2]
int ppre = 0;
// dp[i-1]
int pre = nums[0];
// dp[i]
int cur1 = nums[0];
// 遍歷nums數(shù)組
for (int i = 2; i < nums.size(); i++) {
cur1 = max(pre, ppre + nums[i - 1]);
ppre = pre;
pre = cur1;
}
// 含尾不含頭
ppre = 0;
pre = nums[1];
int cur2 = nums[1];
for (int i = 3; i <= nums.size(); i++) {
cur2 = max(pre, ppre + nums[i - 1]);
ppre = pre;
pre = cur2;
}
// 返回兩個(gè)區(qū)間里的較大者
return max(cur1, cur2);
}
337. 打家劫舍 III
0_復(fù)習(xí)樹(shù)
因?yàn)楦鷺?shù)有關(guān)，我貼一個(gè)遍歷方法出來(lái)：
遞歸法遍歷樹(shù)適用于各種
樹(shù)節(jié)點(diǎn)結(jié)構(gòu)體定義：
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode() : val(0), left(nullptr), right(nullptr) {}
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
TreeNode(int x, TreeNode* left, TreeNode* right) : val(x), left(left), right(right) {}
};
根節(jié)點(diǎn)的構(gòu)造和函數(shù)遍歷函數(shù)調(diào)用：
int main() {
// [3,2,3,null,3,null,1]
TreeNode* root = new TreeNode(3, new TreeNode(2, nullptr, new TreeNode(3)), new TreeNode(3, nullptr, new TreeNode(1)));
postTraval(root);
return 0;
}
遞歸法的后序遍歷
void postTraval(TreeNode* root) {
if (root == nullptr)
return;
// 左右中
if (root->left != nullptr)
postTraval(root->left);
if (root->right != nullptr)
postTraval(root->right);
cout << root->val << " ";
}
迭代法的后續(xù)遍歷：
// 后序遍歷_迭代版
void postTraval(TreeNode* root) {
/*
棧
先存入后訪問(wèn)
空指針標(biāo)記
取節(jié)點(diǎn)時(shí)，判斷是否為空指針
空指針：取出的是需要訪問(wèn)的節(jié)點(diǎn)
非空指針：加上空指針標(biāo)記，便于后續(xù)取出訪問(wèn)
*/
// 數(shù)組做棧，存放遍歷節(jié)點(diǎn)
TreeNode* stack[30] = { 0 };
// 棧頂指針
int top = -1;
// 預(yù)先存入根節(jié)點(diǎn)
stack[++top] = root;
// 迭代父節(jié)點(diǎn)---當(dāng)棧不為空時(shí)，還有節(jié)點(diǎn)尚未遍歷
while (top != -1) {
// 取出節(jié)點(diǎn)
TreeNode* cur = stack[top--];
if (cur != nullptr) {
// 存入節(jié)點(diǎn)---后序遍歷（左右中）---棧的后入先出---（中右左）
// 存入當(dāng)前節(jié)點(diǎn)時(shí)，需要加入標(biāo)記---先入節(jié)點(diǎn)在入空指針
stack[++top] = cur;
stack[++top] = nullptr;
// 存左子節(jié)點(diǎn)
if (cur->right != nullptr)
stack[++top] = cur->right;
// 存右子節(jié)點(diǎn)
if (cur->left != nullptr)
stack[++top] = cur->left;
}
else {
// 進(jìn)行訪問(wèn)---因?yàn)槿〕龅氖强罩羔?，下一個(gè)棧頂才是要訪問(wèn)的節(jié)點(diǎn)
cur = stack[top--];
cout << cur->val << " ";
}
}
}
1_動(dòng)態(tài)規(guī)劃
本題里第一次涉及到樹(shù)狀dp
樹(shù)狀dp和數(shù)組dp只是數(shù)據(jù)結(jié)構(gòu)不同
原理都是在遍歷數(shù)據(jù)時(shí)進(jìn)行狀態(tài)轉(zhuǎn)移
注意狀態(tài)轉(zhuǎn)移的方向
當(dāng)選擇后序遍歷樹(shù)時(shí)，因?yàn)槭窍冗M(jìn)入左右子節(jié)點(diǎn)，所以當(dāng)前狀態(tài)才能從子狀態(tài)中推出
①dp值含義
考慮當(dāng)前節(jié)點(diǎn)及其所有子節(jié)點(diǎn)后，得到的最大值
②遞推公式
選擇兩種情況中的最大值
1° 選擇當(dāng)前節(jié)點(diǎn)，遞歸進(jìn)入孫子節(jié)點(diǎn)
val1=當(dāng)前節(jié)點(diǎn)值+孫子節(jié)點(diǎn)的最大值2° 不選擇當(dāng)前節(jié)點(diǎn)，遞歸進(jìn)入子節(jié)點(diǎn)
val2=左右子節(jié)點(diǎn)的最大值
// 偷當(dāng)前節(jié)點(diǎn)---遞歸進(jìn)入孫子節(jié)點(diǎn)
int val1 = root->val;
// 加入判斷，避免操作空指針
if (root->left != nullptr)
val1 += rob(root->left->left) + rob(root->left->right);
if (root->right != nullptr)
val1 += rob(root->right->left) + rob(root->right->right);
// 不偷當(dāng)前節(jié)點(diǎn)---遞歸進(jìn)入子節(jié)點(diǎn)
int val2 = rob(root->left) + rob(root->right);
③因?yàn)樽訝顟B(tài)直接由各個(gè)節(jié)點(diǎn)值可以直接得出，所以不用初始化
④遍歷順序
選擇后序遍歷樹(shù)
因?yàn)槭?strong>先進(jìn)入左右子節(jié)點(diǎn)，所以當(dāng)前狀態(tài)才能從子狀態(tài)中推出
完整代碼:
int rob(TreeNode* root) {
// 當(dāng)傳入節(jié)點(diǎn)為空時(shí)，返回0
if (root == nullptr)
return 0;
// 傳入節(jié)點(diǎn)非空且無(wú)子節(jié)點(diǎn)時(shí)，返回當(dāng)前節(jié)點(diǎn)值
if (root->left == nullptr && root->right == nullptr)
return root->val;
// 偷當(dāng)前節(jié)點(diǎn)---遞歸進(jìn)入孫子節(jié)點(diǎn)
int val1 = root->val;
// 加入判斷，避免操作空指針
if (root->left != nullptr)
val1 += rob(root->left->left) + rob(root->left->right);
if (root->right != nullptr)
val1 += rob(root->right->left) + rob(root->right->right);
// 不偷當(dāng)前節(jié)點(diǎn)---遞歸進(jìn)入子節(jié)點(diǎn)
int val2 = rob(root->left) + rob(root->right);
// 在兩種情況中返回較大值
return max(val1, val2);
}
2_記憶化搜索（備忘錄）
提交會(huì)發(fā)現(xiàn)有測(cè)試用例超時(shí)，因?yàn)榇嬖诖罅恐貜?fù)計(jì)算
例如：在不考慮當(dāng)前節(jié)點(diǎn)時(shí)，進(jìn)入的左右子節(jié)點(diǎn)可能已經(jīng)通過(guò)之前的孫子節(jié)點(diǎn)計(jì)算過(guò)結(jié)果
所以可以通過(guò)設(shè)置一個(gè)數(shù)據(jù)結(jié)構(gòu)來(lái)記錄每一個(gè)節(jié)點(diǎn)的計(jì)算結(jié)果
數(shù)據(jù)結(jié)構(gòu)的選擇
本題中我們要選擇一個(gè)能夠存儲(chǔ)樹(shù)節(jié)點(diǎn)，并且能夠通過(guò)樹(shù)節(jié)點(diǎn)查詢(xún)到其計(jì)算結(jié)果的數(shù)據(jù)結(jié)構(gòu)
自然會(huì)想到使用map（通過(guò)鍵查詢(xún)值）因?yàn)橥ㄟ^(guò)遞歸遍歷樹(shù)，所以不能選擇在某一層建立map，應(yīng)該開(kāi)全局map
而平時(shí)是數(shù)組，僅需通過(guò)索引查詢(xún)，用數(shù)組做備忘錄就行
完整代碼：
unordered_map<TreeNode*, int> visit;
int rob(TreeNode* root) {
// 當(dāng)傳入節(jié)點(diǎn)為空時(shí)，返回0
if (root == nullptr)
return 0;
// 傳入節(jié)點(diǎn)非空且無(wú)子節(jié)點(diǎn)時(shí)，返回當(dāng)前節(jié)點(diǎn)值
if (root->left == nullptr && root->right == nullptr)
return root->val;
// 在選擇偷法前判斷是否已經(jīng)存在計(jì)算結(jié)果
if (visit.find(root) != visit.end())
return visit[root];
// ②find函數(shù)返回迭代器，通過(guò)second獲取值
// return visit.find(root)->second;
// 偷當(dāng)前節(jié)點(diǎn)---遞歸進(jìn)入孫子節(jié)點(diǎn)
int val1 = root->val;
// 加入判斷，避免操作空指針
if (root->left != nullptr)
val1 += rob(root->left->left) + rob(root->left->right);
if (root->right != nullptr)
val1 += rob(root->right->left) + rob(root->right->right);
// 不偷當(dāng)前節(jié)點(diǎn)---遞歸進(jìn)入子節(jié)點(diǎn)
int val2 = rob(root->left) + rob(root->right);
// 返回前存入結(jié)果
visit[root]=max(val1,val2);
// 插入鍵值對(duì)
// visit.insert(pair<TreeNode*,int>(root,max(val1,val2);
// 在兩種情況中返回較大值
return max(val1, val2);
}
總結(jié)
打家劫舍的dp遞推公式比較容易找到
難的是邊界情況判斷
以及跟樹(shù)結(jié)合時(shí)需要使用備忘錄文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-773622.html
到了這里，關(guān)于動(dòng)態(tài)規(guī)劃_打家劫舍（Ⅰ~Ⅲ）的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
