西安网站推广慧创_外贸网站建站注意事项_手机百度app下载_志鸿优化设计答案网

1.打家劫舍

1.1 题目

. - 力扣（LeetCode）

1.2 题解

class Solution 
{
public:int rob(vector<int>& nums) {if(nums.size()==1)return nums[0];//确实dp数组的含义，dp[i]表示长度为i+1的数组能够偷得最大价值vector<int> dp(nums.size(), 0);//确定递推逻辑//dp[i] = max(dp[i - 2] + nums[i], dp[i - 1]);//初始化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.打家劫舍II

2.1 题目

. - 力扣（LeetCode）

2.2 题解

class Solution 
{
public:int rob(vector<int>& nums) {if (nums.size() == 1)return nums[0];if(nums.size()==2)return max(nums[0],nums[1]);//只考虑首元素，不考虑尾元素vector<int> nums1(nums.begin(), nums.end()-1);int result1 = rob2(nums1);//只考虑尾元素，不考虑首元素vector<int> nums2(nums.begin()+1, nums.end());int result2 = rob2(nums2);return max(result1, result2);}int rob2(vector<int>& nums){//确定dp数组的含义，dp[i]表示nums长度为i+1的数组能够偷取的最大价值vector<int> 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(nums[i] + dp[i - 2], dp[i - 1]);}return dp[nums.size() - 1];}
};

3.打家劫舍III

3.1 题目

. - 力扣（LeetCode）

3.2 题解

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:int rob(TreeNode* root) {//dp数组表示dp[0]表示不偷当前节点，dp[1]表示偷当前节点vector<int> result = reverse(root);return max(result[0], result[1]);}vector<int> reverse(TreeNode* node){//确定递归终止条件if (node == nullptr)return { 0,0 };vector<int> leftdp = reverse(node->left);vector<int> rightdp = reverse(node->right);//偷当前节点int value1 = node->val + leftdp[0] + rightdp[0];//不偷当前节点int value2 = max(leftdp[0], leftdp[1]) + max(rightdp[0], rightdp[1]);return{ value2,value1 };}
};