网站降权 烦,如何让百度新闻收录网站文章,义乌十大进出口贸易公司,自己做的网站可以挂在哪里今天就是打家劫舍的一天,微笑
198.打家劫舍
leetcode题目链接 视频讲解 文章讲解
动规五部曲分析如下#xff1a; 确定dp数组#xff08;dp table#xff09;以及下标的含义 dp[i]#xff1a;考虑下标i#xff08;包括i#xff09;以内的房屋#xff0c;最多可以偷窃…今天就是打家劫舍的一天,微笑
198.打家劫舍
leetcode题目链接 视频讲解 文章讲解
动规五部曲分析如下 确定dp数组dp table以及下标的含义 dp[i]考虑下标i包括i以内的房屋最多可以偷窃的金额为dp[i]。 确定递推公式 决定dp[i]的因素就是第i房间偷还是不偷。
如果偷第i房间那么dp[i] dp[i - 2] nums[i] 即第i-1房一定是不考虑的找出 下标i-2包括i-2以内的房屋最多可以偷窃的金额为dp[i-2] 加上第i房间偷到的钱。
如果不偷第i房间那么dp[i] dp[i - 1]即考 虑i-1房注意这里是考虑并不是一定要偷i-1房这是很多同学容易混淆的点
然后dp[i]取最大值即dp[i] max(dp[i - 2] nums[i], dp[i - 1]);
dp数组如何初始化
从递推公式dp[i] max(dp[i - 2] nums[i], dp[i - 1]);可以看出递推公式的基础就是dp[0] 和 dp[1]
从dp[i]的定义上来讲dp[0] 一定是 nums[0]dp[1]就是nums[0]和nums[1]的最大值即dp[1] max(nums[0], nums[1]);
class Solution {
public:int rob(vectorint nums) {//1. dp数组的含义 是dp[i] 0到i的最优选项不一定包含当前节点vectorint dp(nums.size(), 0);if(nums.size() 0) return 0;if(nums.size() 1) return nums[0];//2. 递推公式//当前节点的结果有两种情况一中是投当前节点一种是不偷当前节点//偷当前节点就是前一个节点的最优解dp[i-1]//不偷当前节点就是前一个节点不能偷所以是dp[i-2] nums[i];//所以递推公式就是 dp[i] max(dp[i-1], dp[i-2] nums[i];//3. 初始化dp[0] nums[0];dp[1] max(nums[0], nums[1]);for(int i 2; i nums.size(); i) {dp[i] max(dp[i-1], dp[i-2] nums[i]);}return dp[nums.size() -1];}
};213.打家劫舍II
leetcode题目链接 视频讲解 文章讲解
将环形数组根据题目描述可以分解为两种数组
// 注意注释中的情况二情况三以及把198.打家劫舍的代码抽离出来了
class Solution {
public:int rob(vectorint 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);}// 198.打家劫舍的逻辑int robRange(vectorint nums, int start, int end) {if (end start) return nums[start];vectorint dp(nums.size());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];}
};337.打家劫舍III
leetcode题目链接 视频讲解 文章讲解 动态规划结合树形结构比较难
class Solution {
public://int dp[2] {0}; dp[0] 表示不偷当前节点dp[1] 表示偷当前节点vectorint robTree(TreeNode * node) {if(node nullptr) return {0,0};vectorint left(2,0);vectorint right(2,0);left robTree(node-left); //左right robTree(node-right);//右// 中后续遍历已知左右的值推出当前节点的值//不偷当前节点就是要偷 左节点和有节点 将左节点偷和不偷的最大值和右节点头或者不偷的最大值加一起int tmp1 max(left[0], left[1]) max(right[0], right[1]);//偷当前节点的话, 就是将当前节点的值加上左节点和有节点都偷的和int tmp2 node-val left[0] right[0];return {tmp1, tmp2};}int rob(TreeNode* root) {vectorint vec(2,0);vec robTree(root);//返回根节点偷或者不偷的最大值return max(vec[0], vec[1]);}
};
