青岛国家高新区建设局网站,电商培训心得体会,成品网站建设,长治网站建设案例198. 打家劫舍#xff08;题目链接#xff1a;力扣#xff08;LeetCode#xff09;官网 - 全球极客挚爱的技术成长平台#xff09;
思路#xff1a;dp题除背包外的另外一类题目#xff0c;重点不在于看前面的情况#xff0c;而在于考虑本节点的情况。一种情况#xf…198. 打家劫舍题目链接力扣LeetCode官网 - 全球极客挚爱的技术成长平台
思路dp题除背包外的另外一类题目重点不在于看前面的情况而在于考虑本节点的情况。一种情况选择本节点另一种情况不选择本节点看哪种情况下的值最大。初始化也有所不同不是简单地dp[0]0,dp[1]1诸如此类dp[1]要考虑dp[0]的大小才能决定。
int rob(vectorint nums) {int size nums.size();if(size 1) return nums[0];vectorint dp(size, 0);dp[0] nums[0];dp[1] max(nums[0], nums[1]);for(int i2; isize; i){dp[i] max(dp[i-2] nums[i], dp[i-1]);}return dp[size-1];
}
213. 打家劫舍 II题目链接力扣LeetCode官网 - 全球极客挚爱的技术成长平台
思路环形数组第一次见dp中这样的设置其实很简单总体上考虑两种情况情况一考虑除数组头外的其他所有元素情况二考虑除数组尾外的其他所有元素。最后取这两个里面的最大值就好。
int robRange(vectorint nums, int start, int end){if(endstart) return nums[end];vectorint dp(nums.size(), 0);dp[start] nums[start];dp[start1] max(nums[start], nums[start1]);for(int istart2; iend; i){dp[i] max(dp[i-2]nums[i], dp[i-1]);}return dp[end];
}int rob(vectorint nums) {int size nums.size();if(size1) return nums[0];int result1 robRange(nums, 0, size-2);int result2 robRange(nums, 1, size-1);return max(result1, result2);
}
337. 打家劫舍 III题目链接力扣LeetCode官网 - 全球极客挚爱的技术成长平台
思路树形dpdp的做法和二叉树的遍历的做法没有很大差异或者说dp的做法就是基于二叉树的遍历做了一点点的改进只是为了让它更像是动态规划。
递归遍历做法
unordered_mapTreeNode*, int umap;
int rob(TreeNode* root) {if(root NULL) return 0;if(root-leftNULL root-rightNULL) return root-val;if(umap[root]) return umap[root];int val1 root-val;if(root-left) val1 rob(root-left-left)rob(root-left-right);if(root-right) val1 rob(root-right-left)rob(root-right-right);int val2rob(root-left)rob(root-right);umap[root] max(val1, val2);return max(val1, val2);
}
其中用umap是为了让树中每个节点只遍历一遍避免反复求值。
dp做法
int rob(TreeNode* root) {vectorint result robTree(root);return max(result[0], result[1]);
}vectorint robTree(TreeNode* cur){if(curNULL) return {0,0};vectorint left robTree(cur-left);vectorint right robTree(cur-right);int val1 cur-val left[1] right[1];int val2 max(left[0], left[1]) max(right[0], right[1]);return {val1, val2};
}
