思路:
-
使用动态规划
-
-
确定dp数组以及下标的含义
- dp[j]的定义为:打劫1-j所房子最多能偷窃到的金额
-
确定递推公式
| |
| dp[i] = max(dp[i - 1], dp[i - 2] + nums[i - 1]); |
-
dp数组如何初始化
| 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]); |
| } |
我的AC代码
| |
| 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()]; |
| } |
| }; |
标准答案
| |
| class Solution { |
| public: |
| int rob(vector<int>& nums) { |
| if (nums.size() == 0) return 0; |
| if (nums.size() == 1) return nums[0]; |
| vector<int> dp(nums.size()); |
| 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]; |
| } |
| }; |
思路:
我的AC代码
| |
| class Solution { |
| public: |
| int robChoose(vector<int>& nums, int start, int length) { |
| vector<int> dp(length + 1, 0); |
| dp[1] = nums[start]; |
| for(int i = 2; i <= length; ++i) { |
| dp[i] = max(dp[i - 1], dp[i - 2] + nums[i + start - 1]); |
| } |
| return dp[length]; |
| } |
| int rob(vector<int>& nums) { |
| if(nums.size() == 0) { |
| return 0; |
| } |
| else if(nums.size() == 1) { |
| return nums[0]; |
| } |
| else if(nums.size() == 2) { |
| return max(nums[0], nums[1]); |
| } |
| return max(robChoose(nums, 0, nums.size() - 1), robChoose(nums, 1, nums.size() - 1)); |
| } |
| }; |
标准答案
| |
| |
| 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]; |
| } |
| }; |
思路:
- 树形DP的入门题目,使用后序遍历,因为每个节点都有两个状态,偷或者不偷,所以递归的时候需要返回一个只有两个元素的
vector<int>
,用来记录偷和不偷时的最大价值,然后自底部向上,最终得到答案。需要注意的是,若选择偷该节点,那么其两个孩子不能偷,若选择不偷该节点,则可以考虑两个孩子
我的AC代码
| |
| class Solution { |
| public: |
| int rob(TreeNode* root) { |
| return max(ans(root)[0], ans(root)[1]); |
| } |
| |
| vector<int> ans(TreeNode* root) { |
| if(root == nullptr) { |
| return vector<int>{0, 0}; |
| } |
| |
| vector<int> left = ans(root->left); |
| vector<int> right = ans(root->right); |
| |
| int val1 = max(left[0], left[1]) + max(right[0], right[1]); |
| |
| int val2 = root->val + left[0] + right[0]; |
| |
| return {val1, val2}; |
| } |
| }; |
标准答案
| |
| class Solution { |
| public: |
| int rob(TreeNode* root) { |
| vector<int> result = robTree(root); |
| return max(result[0], result[1]); |
| } |
| |
| vector<int> robTree(TreeNode* cur) { |
| if (cur == NULL) return vector<int>{0, 0}; |
| vector<int> left = robTree(cur->left); |
| vector<int> 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}; |
| } |
| }; |
Comments NOTHING