岱山县网站建设,做网站的主营业务,群晖frp 外网访问wordpress,网络规划设计师 招聘1、LeetCode198打家劫舍
题目链接#xff1a;198、打家劫舍
1、dp[i]#xff1a;考虑下标i#xff08;包括i#xff09;以内的房屋#xff0c;最多可以偷窃的金额为dp[i]。
2、递推公式#xff1a;
如果偷第i房间#xff0c;那么dp[i] dp[i - 2] nums[i] #xf…1、LeetCode198打家劫舍
题目链接198、打家劫舍
1、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] 和 dp[1]。
dp[0] nums[0];
dp[1] max(nums[0], nums[1]);
4、遍历顺序 从前向后遍历
5、举例推导。
class Solution {
public:int rob(vectorint nums) {if (nums.size() 0) return 0;if (nums.size() 1) return nums[0];vectorint 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];}
};
2、LeetCode213打家劫舍II
题目链接213、打家劫舍II
本题首尾连在一起成环有三种情况
考虑不包含首尾元素 考虑包含首元素不包含尾元素 考虑包含尾元素不包含首元素。
第二第三中情况包括第一种所以只需考虑去掉首元素去掉尾元素这两种情况下哪种的dp[i]更大。
递归五部曲与上题一样由于要去掉首尾元素定义一个start、end区间
robRange(vectorint nums, int start, int end)。
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);}int robrange(vectorint nums, int start, int end){if (start end) return nums[start];vectorint dp(nums.size(), 0);dp[start] nums[start];dp[start1] max(nums[start], nums[start1]);for (int i start 2; i end; i){dp[i] max(dp[i-2] nums[i], dp[i-1]);}return dp[end];}
};
3、LeetCode337打家劫舍III
题目链接337、打家劫舍III
第一次做树形dp有点难理解。
1、dp数组dp table以及下标的含义下标为0记录不偷该节点所得到的的最大金钱下标为1记录偷该节点所得到的的最大金钱。
2、递归树时的终止条件
如果遇到空节点的话无论偷还是不偷都是0。
if (cur NULL) return vectorint{0,0}; 注意这里是花括号。
3、遍历顺序
后序遍历。
递归左节点得到左节点偷与不偷的金钱。
递归右节点得到右节点偷与不偷的金钱。
4、递推公式
偷该节点则左右孩子不能偷int val1 cur-val left[0] left[1]
不偷该节点则左右孩子要偷每个孩子里偷一个最大的int val2 max(left[0],left[1]) max(right[0], right[1])
最后当前节点的状态就是{val2, val1}; 即{不偷当前节点得到的最大金钱偷当前节点得到的最大金钱}。
5、举例推导 class Solution {
public:int rob(TreeNode* root) {vectorint result robTree(root);return max(result[0], result[1]);}vectorint robTree(TreeNode* cur){if (cur NULL) return vectorint{0,0};vectorint left robTree(cur-left);vectorint right robTree(cur-right);int val1 cur-val left[0] right[0];int val2 max(left[0], left[1]) max(right[0], right[1]);return {val2,val1};}
};
