本文主要是介绍DAY52：动态规划（打家劫舍系列），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
Leetcode: 198 打家劫舍
基本思路
1、dp下标
dp[i]表示下标i（包括i）以内的房屋，最多可以偷窃的金额为dp[i]。
2、递推公式
如果偷第i房间，那么dp[i] = dp[i - 2] + nums[i]。
如果不偷第i房间，那么dp[i] = dp[i - 1]。
所以dp[i]取最大值，即dp[i] = max(dp[i - 2] + nums[i], dp[i - 1]);
3、初始化
dp[0]为num[0]，dp[1]为max(num[0],num[1])
时间复杂度: O(n)
空间复杂度: O(n)
class Solution {
public:int rob(vector<int>& nums) {if (nums.size() == 0) return 0;//注意先对特殊情况进行剪枝if (nums.size() == 1) return nums[0];vector<int> dp(nums.size(), 0);dp[0] = nums[0];//初始化dp[1] = max(nums[0], nums[1]);for(int i = 2; i < nums.size();i++){dp[i] = max(dp[i - 2] + nums[i], dp[i - 1]);//递推公式}return dp[nums.size() - 1];}
};Leetcode: 213 打家劫舍II
与上题不同点在于，这个地方所有的房屋都围成一圈 ，这意味着第一个房屋和最后一个房屋是紧挨着的。唯一差别在于环的出现。
可以分为两种情况
1、考虑首元素，不考虑尾元素
2、考虑尾元素，不考虑首元素
因此只需要这两种情况都考虑，选一个最大的就可以。
可以写成统一的函数。也可以写两遍。
时间复杂度: O(n)
空间复杂度: O(n)
class Solution {
public:int rob(vector<int>& nums) {if (nums.size() == 0) return 0;//注意先对特殊情况进行剪枝if (nums.size() == 1) return nums[0];int result1 = findresult(nums, 0, nums.size() - 2);//考虑首int result2 = findresult(nums, 1, nums.size() - 1);//考虑尾return max(result1, result2);}int findresult(vector<int>& nums , int start, int end){if(start == end) 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 - 2] + nums[i], dp[i - 1]);}return dp[end];//返回结果}
};Leetcode: 337 打家劫舍III
与上两题不同，是因为这道题房屋是按照二叉树来进行排列的，因此涉及到树的遍历问题。
树形dp
因为动态规划函数需要通过数据进行计算，所以需要后序遍历，按照左右中的顺序来。
代码随想录
基本思路
1、确定递归函数的参数和返回值
这里我们要求一个节点 偷与不偷的两个状态所得到的金钱，那么返回值就是一个长度为2的数组。
所以dp数组[0]存储不偷该节点的最大金钱，[1]存储偷该节点的最大金钱。
2、确定终止条件
在遍历的过程中，如果遇到空节点的话，很明显，无论偷还是不偷都是0，所以就返回{0,0}
3、遍历顺序
后序遍历
4、递归逻辑
如果是偷当前节点，那么左右孩子就不能偷，val1 = cur->val + left[0] + right[0];
如果不偷当前节点，那么左右孩子就可以偷，至于到底偷不偷一定是选一个最大的，所以：val2 = max(left[0], left[1]) + max(right[0], right[1]);
时间复杂度：O(n)
空间复杂度：O(log n)
class Solution {
public:int rob(TreeNode* root) {vector<int> result = robTree(root);return max(result[0], result[1]);}vector<int> robTree(TreeNode* cur) {if(cur == NULL) return vector<int>{0,0};vector<int> left = robTree(cur->left);//左vector<int> right = robTree(cur->right);//右//dp状态转移公式,中// 偷cur，那么就不能偷左右节点。int val1 = cur->val + left[0] + right[0];// 不偷cur，那么可以偷也可以不偷左右节点，则取较大的情况int val2 = max(left[0], left[1]) + max(right[0], right[1]);return {val2, val1};}
};这篇关于DAY52：动态规划（打家劫舍系列）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
