摘要
如果一步选择会受之前的选择影响，可以考虑是否能使用动态规划。
不需要遍历环的所有可能序列，只需要从某个位置将环拆开。
树形 dp 要结合二叉树遍历和动态规划的思路，先划分各个节点的状态，再根据节点的位置关系求递推公式，然后根据状态更新的先后顺序确定二叉树的遍历方式。
LeetCode198 打家劫舍
偷，还是不偷？先直观地来思考一下。如果当前房屋相邻的房屋已经被偷过，那当然是不能再偷的。之前选取的要偷的房屋也不一定能让总金额最大，所以也不能只凭相邻的房屋有没有被偷就决定偷不偷当前房屋。但是，当前房屋能不能选，会受之前房屋状态的影响，所以考虑使用动态规划来解决问题。
确定
dp数组和数组下标的含义：dp[i]表示，尝试偷从第0所到第i所房屋，偷的房屋不相邻，能偷取的最大金额。-
确定递推公式，从简单的子问题开始
- 只尝试一间房屋，即只有第
0号房屋时，当然是就偷这一间房能得到最大金额，不偷就一分钱没有了。所以 - 只有两间房屋，第
0号房屋和第1号房屋相邻，所以只能偷其中一间，那当然是偷其中金额较大的那间，能使得偷到的总金额最大。所以 - 只有三间房屋，偷的房屋互不相邻，那就有两种偷取方案：1）偷第
0号房屋和第2号房屋；2）偷第1号房屋，就不能再偷2。所以 - 推广到有
n间房屋，现在要判断第i号房屋要不要偷，假设前面从0到i-1号房屋已经得到了最大金额的方案，即dp[i-1]和dp[i-2]已知。- 第
i号房屋可以偷，说明第i-1号房屋没有被偷，则；
- 第
i号房屋不可以偷，说明i-1号房屋被偷了，所以
- 第
- 得到如下递推公式
- 只尝试一间房屋，即只有第
初始化
dp数组时，要注意输入的nums对应有多少间房屋，防止下标越界。根据递推公式，
dp[i]的更新依赖于dp[i-1]和dp[i-2]，所以应该i从小到大来更新dp数组。
题解代码如下
class Solution {
public:
int rob(vector<int>& nums) {
if (nums.size() == 0) return 0;
vector<int> dp(nums.size(), 0);
dp[0] = nums[0];
if (nums.size() == 1) return dp[0];
dp[1] = max(nums[0], nums[1]);
if (nums.size() == 2) return dp[1];
for (int i = 2; i < dp.size(); i++) {
dp[i] = max(dp[i - 1], dp[i - 2] + nums[i]);
}
return dp[dp.size() - 1];
}
};
LeetCode213 打家劫舍II
这题和上一题是类似的，唯一的区别就是房屋不再是一个一维数组，而是一个环。
-
如果能将环转化为一维数组的情况，就可以用上一题的方法来解决。我是用拆环的方式来理解的
- 元素个数为
n的环，分别以每个元素为起点，能得到n个序列。那是不是说要分别以每间房屋作为起点，将环转化为n个一维数组，然后对每个一维数组更新一轮dp数组，最后求得每轮更新中的dp数组中保存的最大值。 - 需要更新
n轮dp数组吗？可以，但是没有必要。实际上，只需要通过删除nums[0]或nums.back()，把环拆开，分别对这两种拆法得到的序列求最大金额。最后从这两个最大金额中取更大的那个就是答案。 - 实际上，从哪里拆开都是一样的，不过删掉头或者删掉尾比较方便实现拆开环。
- 元素个数为
-
直观地来理解，其实删掉头和删掉尾就对应两种情况
- 直接假设不偷
nums[0]，dp数组的初始化和更新过程中直接忽略nums[0] - 直接假设不偷
nums.back()，dp数组的初始化和更新过程中直接忽略nums.back()
- 直接假设不偷
最后再综合这两种情况来取最大值，排除忽略
nums[0]和忽略nums.back()对计算的影响。取得最大的总金额时，无非就是不取
nums[0]或不取nums.back()或两者都不取。而直接假设不偷nums[0]和直接假设不偷nums.back()就包含了两个都不偷的情况。相当于我们把取最大总金额时分情况讨论。
题解代码如下
class Solution {
public:
int rob(vector<int>& nums) {
if (nums.size() == 0) return 0;
if (nums.size() == 1) return nums[0];
if (nums.size() == 2) return max(nums[0], nums[1]);
vector<int> dp(nums.size(), 0);
int res = 0;
dp[0] = nums[0];
dp[1] = max(dp[0], nums[1]);
for (int i = 2; i < nums.size() - 1; i++) {
dp[i] = max(dp[i - 1], dp[i - 2] + nums[i]);
}
res = max(dp[dp.size() - 2], res);
fill(dp.begin(), dp.end(), 0);
dp[1] = nums[1];
dp[2] = max(dp[1], nums[2]);
for (int i = 3; i < nums.size(); i++) {
dp[i] = max(dp[i - 1], dp[i - 2] + nums[i]);
}
res = max(dp[dp.size() - 1], res);
return res;
}
};
LeetCode337 打家劫舍III
- 这道题目是一道树形 dp 的入门题目。关键在于如何将二叉树遍历和动态规划的思路结合起来。树形 dp 的思考步骤和一般的动态规划有所不同。
划分每个节点的状态，确定
dp数组及数组下标的含义。本题中，每个节点只有不偷（设为0）和偷（设为1）两种状态，dp[0]表示不偷当前节点能得到的最大金额，dp[1]表示偷当前节点。-
确定状态转移方程，先看简单的子问题，
left和right分别表示当前节点的左孩子和右孩子的dp数组。- 空节点，
dp = {0, 0}，这样就可以使得叶节点与非叶节点的操作统一起来。 - 对于一个节点，如果选择偷这个节点，就不能偷它的左孩子和右孩子，所以当前节点的
dp[1] = left[0] + right[0]；如果不偷这个节点，它的左孩子和右孩子就是可偷可不偷，要判断左孩子和右孩子怎么偷才能得到最大金额，即dp[0] = max(left[0], left[1]) + max(right[0], right[1])。
- 空节点，
- 确定
dp数组如何初始化，其实也是在确定递归函数的终止条件，由上面推导递推公式的过程，遇到空节点时应该返回{0, 0}，这也相当于初始化了dp数组。 - 遍历顺序，由于当前节点的
dp数组更新依赖于它的左孩子和右孩子，所以应该使用后序遍历，自底向上的更新每个节点的dp数组。
题解代码如下
class Solution {
public:
vector<int> robWorkPlace(TreeNode* node) {
if (!node) return {0, 0};
vector<int> left = robWorkPlace(node->left);
vector<int> right = robWorkPlace(node->right);
int dp0 = max(left[0], left[1]) + max(right[0], right[1]);
int dp1 = node->val + left[0] + right[0];
return {dp0, dp1};
}
int rob(TreeNode* root) {
if (!root) return 0;
vector<int> dp = robWorkPlace(root);
return max(dp[0], dp[1]);
}
};
以 LeetCode 的示例 1 为例，模拟dp数组的计算过程
- 后序遍历，先到第一个叶节点，左下角的
3，计算出dp数组
- 然后返回到第二层的值为
2的节点，不选当前节点能得到的最大金额为3，选当前节点能得到的最大金额为2。
- 然后根据后序遍历，到右下角的叶节点，即值为
1的节点
- 返回到第二层的值为
3的节点
- 最后返回到根节点
