代码随想录算法训练营day39

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 };
	}
};