代码随想录算法训练营 Day39 动态规划Ⅶ 打家劫舍

动态规划

题目

198. 打家劫舍 - 力扣（LeetCode）
Dp 容量为 nums. Size ()+1，表示 dp 时打劫前 i 房子最大金币，前一个房子是 nums[i-1]
1. Dp 表示打劫前 i 房子获得的最大金币
2. 递推公式 dp[i]=max(dp[i-1], dp[i-2] + nums[i-1])
如果当前房价偷了，前一个不能偷，如果当前房价没偷，可以考虑偷不偷之前房
3. 公式得出递推关系从 i-1,i-2 推出，因此要初始化 dp[0], dp[1]
初始化得到 dp[0]=0, dp[1] = nums[0]
4. 遍历顺序通过递推关系得到从前往后
5. 打印 dp

int rob(vector<int>& nums) {// dp打劫前i个房子获得最大金币vector<int> dp(nums.size()+1, 0);dp[0] = 0;dp[1] = nums[0];// 遍历dpfor (int i = 2; i <= nums.size(); ++i) {dp[i] = max(dp[i-1], dp[i-2] + nums[i-1]);}return dp[nums.size()];
}

213. 打家劫舍 II - 力扣（LeetCode）
成环问题解决，1. 去掉头尾链接看作线性数组解决，2. 考虑首元素不考虑尾元素，3. 只考虑尾元素
将情况 2 3 进行线性的选择 (2 3 包括了情况 1)，然后取两者最大值完成本题目
1. Dp 表示打劫前 i 个房子获得最大金币
2. 递推公式表示 dp[i] = max(dp[i-1], dp[i-2]+nums[i])
3. 初始化 dp[start] = 0, dp[start+1] = nums[start]
4. 遍历顺序从前到后
5. 打印 dp

int rob(vector<int>& nums) {if (nums.size() == 0) return 0;if (nums.size() == 1) return nums[0];int res1 = robKernel(nums, 0, nums.size()-1);int res2 = robKernel(nums, 1, nums.size());return std::max(res1, res2);
}// 单独的打家劫舍问题
int robKernel(vector<int>& nums, int start, int end) {// 定义dp数组 打劫前i房屋最大金币数if (start == end) return nums[start];vector<int> dp(nums.size()+1, 0);dp[start] = 0;dp[start+1] = nums[start];// 遍历dp数组for (int i = start+2; i <= end; ++i) {dp[i] = std::max(dp[i-1], dp[i-2] + nums[i-1]);}return dp[end];
}

337. 打家劫舍 III - 力扣（LeetCode）
树形 dp 问题，首先考虑树
1. 二叉树返回值每层返回当前层 dp 状态偷与不偷的值
2. 二叉树终止条件：遍历到叶子节点终止
3. 二叉树的单层递归逻辑：按照后序遍历，将结果从叶子往根传递
Dp 分析五部曲
A. dp 定义为 dp[0] dp[1] 表示不偷当前节点与偷当前节点，规定 0 表示不偷 1 表示偷
B. 递推公式两种状态
res 1 偷当前节点，那就取子节点不偷 res1 = cur->val + left[0], right[0]
Res 2 不偷当前节点
选择子节点的最大情况 res 2=max(left[0], left[1]) + max(right[0], right[1])
C. 初始化默认为 0
D. 遍历顺序跟随树的后序遍历（将结果逐个返回上一个节点）
E. 打印 dp 数组
DP 流程推导，从叶子结点开始，如果给出两个 res
不偷当前 dp[0]=max(0,0) 与偷当前 dp[1]=3+0+0
接着 2 数值的节点选择不偷叶子 dp[0]=max(0,3) 偷当前 dp[1]=2+0
以此类推直到遍历到根节点

std::vector<int> robTree(TreeNode* cur) {// 终止条件 规定 dp[0]表示不偷情况 dp[1]表示偷情况if (cur == nullptr) return std::vector<int> {0,0};// 单层遍历顺序（后序遍历）std::vector<int> left = robTree(cur->left);std::vector<int> right = robTree(cur->right);// 中 res1表示偷当前(偷当前子节点选择不偷) res2表示不偷当前(子节点批判性偷取，选择最大)int res1 = cur->val + left[0] + right[0];int res2 = std::max(left[0], left[1]) + std::max(right[0], right[1]);// 返回vector<int> 不偷当前 偷当前return {res2, res1};
}int rob(TreeNode* root) {std::vector<int> res = robTree(root);return std::max(res[0], res[1]);
}