所有的LeetCode題解索引，可以看這篇文章——【算法和數(shù)據(jù)結(jié)構(gòu)】LeetCode題解。

一、198、打家劫舍

??思路分析：打家劫舍是動態(tài)規(guī)劃的的經(jīng)典題目。本題的難點在于遞歸公式和初始化。

• 第一步，$dp[j]$的含義。$dp[j]$代表到第$j$家的時候，偷竊到的最高金額。
• 第二步，遞推公式。$dp[j]$僅僅與$dp[j?1]$和$dp[j?2]$有關(guān)。如果不偷第$j$家，則偷竊金額不變，$dp[j]=dp[j?1]$。如果偷第$j$家，那么偷竊金額在$dp[j?2]$基礎(chǔ)上加上$nums[i]$，即$dp[j]=dp[j?2]+nums[i]$。綜合二者，$dp[j]=max(dp[j?1],dp[j?2]+nums[i])$。
• 第三部，元素初始化。$dp[0]$初始化為0，代表還沒開始偷竊；$dp[1]$初始化為$num[0]$。
• 第四部，遞歸順序。循環(huán)從$j=2$開始。
• 第五步，打印結(jié)果。
  ??程序如下：

// 198、打家劫舍，動態(tài)規(guī)劃
class Solution {
public:int rob(vector<int>& nums) {vector<int> dp(nums.size() + 1, 0);dp[1] = nums[0];for (int i = 2; i <= nums.size(); i++) {dp[i] = max(dp[i - 1], dp[i - 2] + nums[i-1]);}return dp[nums.size()];}
};

復(fù)雜度分析：

• 時間復(fù)雜度： $O(n)$。
• 空間復(fù)雜度：$O(n)$。

??因為只用到了dp數(shù)組的最后一個元素，實際上不需要保存所有的元素。因此對上述代碼進(jìn)行內(nèi)存優(yōu)化，將空間復(fù)雜度降低到$O(1)$，但是遞歸的過程不明顯，找bug費勁。

// 198、打家劫舍，動態(tài)規(guī)劃-內(nèi)存優(yōu)化
class Solution2 {
public:int rob(vector<int>& nums) {if (nums.size() == 0) return 0;if (nums.size() == 1) return nums[0];int first = nums[0], second = max(nums[0], nums[1]);for (int i = 2; i < nums.size(); i++) {int temp = second;second = max(second, first + nums[i]);first = temp;}return second;}
};

復(fù)雜度分析：

• 時間復(fù)雜度： $O(n)$。
• 空間復(fù)雜度：$O(1)$。

二、213、打家劫舍 II

??思路分析：本題是打家劫舍I的升級版，要求第一家和最后一家是連著的，不能同時偷。這是一個非此即彼的問題。要么偷第一家，不偷最后一家，這等于將最后一家排除在外。反之，不偷第一家，偷最后一家，等價于將第一家排除在外。假設(shè)第一家的下標(biāo)為$0$，最后一家的下標(biāo)為$i?1$，那么一共有兩種情況：偷竊范圍$[0,i?2]$，偷竊范圍$[1,i?1]$。然后應(yīng)用打家劫舍I的思路來做即可。以下是動態(tài)規(guī)劃的代碼，內(nèi)存優(yōu)化版本就沒給出了，思路都是一樣的。

??程序如下：

// 213、打家劫舍II，動態(tài)規(guī)劃
class Solution3 {
public:int rob(vector<int>& nums) {if (nums.size() == 0) return 0;if (nums.size() == 1) return nums[0];int result1 = robRange(nums, 0, nums.size() - 2);int result2 = robRange(nums, 1, nums.size() - 1);return max(result1, result2);}int robRange(vector<int>& nums, int start, int end) {if (end == start) return nums[start];vector<int> dp(nums.size(), 0);dp[start] = nums[start];dp[start + 1] = max(nums[start], nums[start + 1]);for (int i = start + 2; i <= end; i++) {dp[i] = max(dp[i - 1], dp[i - 2] + nums[i - 1]);}return dp[end];}
};

復(fù)雜度分析：

• 時間復(fù)雜度： $O(n)$。
• 空間復(fù)雜度：$O(n)$。

三、337、打家劫舍III

??思路分析：本題是打家劫舍I的變體，原題目中的數(shù)組變成了二叉樹。本題涉及到樹形遞歸和動態(tài)規(guī)劃，我們就結(jié)合遞歸三部曲和動態(tài)規(guī)劃五步驟：

• 1、返回值和遞歸參數(shù)。我們需要判斷一個節(jié)點要不要偷，而偷不偷取決于動作帶來的收益。因此，我們需要返回一個節(jié)點偷與不偷的兩個狀態(tài)所得的金額。這就是一個長度為2的數(shù)組。這里我們假設(shè)這個二維數(shù)組第一個元素代表不偷的收益，第二個元素代表偷的收益，{$0,1=不偷的收益，偷的收益$}。輸入?yún)?shù)是當(dāng)前節(jié)點。
• 2、確定終止條件。當(dāng)遇到空節(jié)點就返回，空節(jié)點不會帶來收益。因此返{$0,0$}。

	if (cur == NULL) return vector<int>{0, 0};

• 3、確定遍歷順序。因為當(dāng)前節(jié)點偷不偷需要根據(jù)左右孩子的返回值來進(jìn)行判斷，所以 我們需要先得到左右孩子的返回值，即先遍歷左右孩子。在所有的遍歷順序中，只有后序遍歷（左右中遍歷順序）滿足。

	vector<int> left = robTree(cur->left); // 左vector<int> right = robTree(cur->right); // 右

• 4、確定單層遞歸邏輯。對于當(dāng)前節(jié)點來說，只有兩個情況。如果偷當(dāng)前節(jié)點，那么左右孩子節(jié)點就不能偷，偷的收益=左孩子不偷的收益+右孩子不偷的收益。如果不偷當(dāng)前節(jié)點，那么左右孩子節(jié)點可偷可不偷，至于究竟偷不偷就看那個收益大（注意偷的收益未必更大，偷了小的金額，旁邊大的金額就偷不了）。不偷的收益 = max（左孩子不偷的收益，左孩子偷的收益）+max（右孩子不偷的收益，右孩子偷的收益）。將文字抽象成公式：

 	int val1 = cur->val + left[0] + right[0];   // 偷當(dāng)前節(jié)點，那么左右孩子節(jié)點不能偷int val2 = max(left[0], left[1]) + max(right[0], right[1]); // 不偷當(dāng)前節(jié)點，那么左右孩子節(jié)點可以偷也可以不偷，取決于偷或者是不偷的金額。

• 5、具體示例推導(dǎo)dp數(shù)組，驗證。
  ??程序如下：

// 337、打家劫舍III動態(tài)規(guī)劃
class Solution {
public:int rob(TreeNode* root) {vector<int> result = robTree(root);return max(result[0], result[1]);}vector<int> robTree(TreeNode* cur) {    // 返回一個二維數(shù)組， {0， 1} = {不偷的金額，偷的金額}if (cur == NULL) return vector<int>{0, 0};vector<int> left = robTree(cur->left);vector<int> right = robTree(cur->right);int val1 = cur->val + left[0] + right[0];   // 偷當(dāng)前節(jié)點，那么左右孩子節(jié)點不能偷int val2 = max(left[0], left[1]) + max(right[0], right[1]); // 不偷當(dāng)前節(jié)點，那么左右孩子節(jié)點可以偷也可以不偷，取決于偷或者是不偷的金額。return { val2, val1 };}
};

復(fù)雜度分析：

• 時間復(fù)雜度： $O(n)$，每個節(jié)點只遍歷了一次。
• 空間復(fù)雜度：$O(logn)$，算上遞推系統(tǒng)棧的空間。

三、完整代碼

// 打家劫舍I, II
# include <iostream>
# include <vector>
# include <algorithm>
using namespace std;// 198、打家劫舍，動態(tài)規(guī)劃
class Solution {
public:int rob(vector<int>& nums) {vector<int> dp(nums.size() + 1, 0);dp[1] = nums[0];for (int i = 2; i <= nums.size(); i++) {dp[i] = max(dp[i - 1], dp[i - 2] + nums[i-1]);}return dp[nums.size()];}
};// 198、打家劫舍，動態(tài)規(guī)劃-內(nèi)存優(yōu)化
class Solution2 {
public:int rob(vector<int>& nums) {if (nums.size() == 0) return 0;if (nums.size() == 1) return nums[0];int first = nums[0], second = max(nums[0], nums[1]);for (int i = 2; i < nums.size(); i++) {int temp = second;second = max(second, first + nums[i]);first = temp;}return second;}
};// 213、打家劫舍II，動態(tài)規(guī)劃
class Solution3 {
public:int rob(vector<int>& nums) {if (nums.size() == 0) return 0;if (nums.size() == 1) return nums[0];int result1 = robRange(nums, 0, nums.size() - 2);int result2 = robRange(nums, 1, nums.size() - 1);return max(result1, result2);}int robRange(vector<int>& nums, int start, int end) {if (end == start) return nums[start];vector<int> dp(nums.size(), 0);dp[start] = nums[start];dp[start + 1] = max(nums[start], nums[start + 1]);for (int i = start + 2; i <= end; i++) {dp[i] = max(dp[i - 1], dp[i - 2] + nums[i - 1]);}return dp[end];}
};int main() {vector<int> nums = { 1,2,3,1 };Solution3 s1;int result = s1.rob(nums);cout << result << endl;system("pause");return 0;
}

// 337、打家劫舍III
# include <iostream>
# include <vector>
# include <string>
# include <queue>
using namespace std;// 樹節(jié)點定義
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) {}
};template<typename T>
void my_print(T& v, const string msg)
{cout << msg << endl;for (class T::iterator it = v.begin(); it != v.end(); it++) {cout << *it << ' ';}cout << endl;
}template<class T1, class T2>
void my_print2(T1& v, const string str) {cout << str << endl;for (class T1::iterator vit = v.begin(); vit < v.end(); ++vit) {for (class T2::iterator it = (*vit).begin(); it < (*vit).end(); ++it) {cout << *it << ' ';}cout << endl;}
}// 前序遍歷迭代法創(chuàng)建二叉樹，每次迭代將容器首元素彈出（彈出代碼還可以再優(yōu)化）
void Tree_Generator(vector<string>& t, TreeNode*& node) {if (!t.size() || t[0] == "NULL") return;    // 退出條件else {node = new TreeNode(stoi(t[0].c_str()));    // 中if (t.size()) {t.assign(t.begin() + 1, t.end());Tree_Generator(t, node->left);              // 左}if (t.size()) {t.assign(t.begin() + 1, t.end());Tree_Generator(t, node->right);             // 右}}
}// 層序遍歷
vector<vector<int>> levelOrder(TreeNode* root) {queue<TreeNode*> que;if (root != NULL) que.push(root);vector<vector<int>> result;while (!que.empty()) {int size = que.size();  // size必須固定, que.size()是不斷變化的vector<int> vec;for (int i = 0; i < size; ++i) {TreeNode* node = que.front();que.pop();vec.push_back(node->val);if (node->left) que.push(node->left);if (node->right) que.push(node->right);}result.push_back(vec);}return result;
}// 337、打家劫舍III動態(tài)規(guī)劃
class Solution {
public:int rob(TreeNode* root) {vector<int> result = robTree(root);return max(result[0], result[1]);}vector<int> robTree(TreeNode* cur) {    // 返回一個二維數(shù)組， {0， 1} = {不偷的金額，偷的金額}if (cur == NULL) return vector<int>{0, 0};vector<int> left = robTree(cur->left);vector<int> right = robTree(cur->right);int val1 = cur->val + left[0] + right[0];   // 偷當(dāng)前節(jié)點，那么左右孩子節(jié)點不能偷int val2 = max(left[0], left[1]) + max(right[0], right[1]); // 不偷當(dāng)前節(jié)點，那么左右孩子節(jié)點可以偷也可以不偷，取決于偷或者是不偷的金額。return { val2, val1 };}
};int main() {vector<string> t = { "3", "2", "NULL", "3", "NULL", "NULL", "3", "NULL", "1", "NULL", "NULL"};   // 前序遍歷TreeNode* root = new TreeNode();    // 生成根節(jié)點Tree_Generator(t, root);            // 生成樹vector<vector<int>> tree = levelOrder(root);    // 層序遍歷my_print2<vector<vector<int>>, vector<int>>(tree, "目標(biāo)樹:");  // 打印層序遍歷Solution s1;int result = s1.rob(root);cout << "最大金額為：" << result << endl;system("pause");return 0;
}

end