算法训练营第五十天 | LeetCode 198 打家劫舍、LeetCode 213 打家劫舍II、LeetCode 337 打家劫舍III

LeetCode 198 打家劫舍

---

代码如下：

class Solution {
public:int rob(vector<int>& nums) {vector<int> dp(nums.size() + 1, 0);dp[1] = nums[0];for (int i = 2; i <= nums.size(); i++) {dp[i] = max(dp[i - 1] ,dp[i - 2] + nums[i - 1]);}return dp[nums.size()];}
};

LeetCode 213 打家劫舍II

---

分情况进行讨论即可

class Solution {
public:int rob(vector<int>& 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(vector<int>& nums, int start, int end) {if (end == start) return nums[start];vector<int> 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];}
};

LeetCode 137 打家劫舍III

---

直接用简单版递归会超时

class Solution {public int innerRob(int state, TreeNode root) {if (root == null) return 0;if (state == 1) {return (innerRob(0, root.left) + innerRob(0, root.right));} else {return Math.max(root.val + innerRob(1, root.left) + innerRob(1, root.right), innerRob(0, root.left) + innerRob(0, root.right));}}public int rob(TreeNode root) {if (root == null) return 0;return Math.max(root.val + innerRob(1, root.left) + innerRob(1, root.right), innerRob(0, root.left) + innerRob(0, root.right));}
}

用哈希表记录下重复子问题就没问题了

class Solution {Map<TreeNode, Integer> choose = new HashMap<TreeNode, Integer>();Map<TreeNode, Integer> not_choose = new HashMap<TreeNode, Integer>();public void dfs (TreeNode root) {if (root == null) return;dfs(root.left);dfs(root.right);choose.put(root, root.val + not_choose.getOrDefault(root.left,0) + not_choose.getOrDefault(root.right,0));not_choose.put(root,Math.max(Math.max(choose.getOrDefault(root.left,0) + choose.getOrDefault(root.right,0), not_choose.getOrDefault(root.left,0) + not_choose.getOrDefault(root.right,0)),Math.max(choose.getOrDefault(root.left,0) + not_choose.getOrDefault(root.right,0), not_choose.getOrDefault(root.left,0) + choose.getOrDefault(root.right,0))));}public int rob(TreeNode root) {dfs(root);return Math.max(choose.getOrDefault(root,0), not_choose.getOrDefault(root,0));}
}

优化后代码如下：

class Solution {Map<TreeNode, Integer> choose = new HashMap<TreeNode, Integer>();Map<TreeNode, Integer> not_choose = new HashMap<TreeNode, Integer>();public void dfs (TreeNode root) {if (root == null) return;dfs(root.left);dfs(root.right);choose.put(root, root.val + not_choose.getOrDefault(root.left,0) + not_choose.getOrDefault(root.right,0));not_choose.put(root,Math.max(choose.getOrDefault(root.left,0), not_choose.getOrDefault(root.left,0)) + Math.max(choose.getOrDefault(root.right,0), not_choose.getOrDefault(root.right,0)));}public int rob(TreeNode root) {dfs(root);return Math.max(choose.getOrDefault(root,0), not_choose.getOrDefault(root,0));}
}