class Solution {
public:
// 决定dp[i]的因素就是第i房间偷还是不偷。
// 偷第i房间，那么dp[i] = dp[i - 2] + nums[i] 即：第i-1房一定是不考虑的，找出 下标i-2（包括i-2）以内的房屋，最多可以偷窃的金额为dp[i-2] 加上第i房间偷到的钱。
// 不偷第i房间，那么dp[i] = dp[i - 1]，即考 虑i-1房，（注意这里是考虑，并不是一定要偷i-1房）
// 然后dp[i]取最大值，即dp[i] = max(dp[i - 2] + nums[i], dp[i - 1]);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[i] = max(dp[i - 2] + nums[i], dp[i - 1]);可以看出，递推公式的基础就是dp[0] 和 dp[1]dp[1] = max(nums[0], nums[1]);//从dp[i]的定义上来讲，dp[0] 一定是 nums[0]，dp[1]就是nums[0]和nums[1]的最大值即：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];}
};

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(10010);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];}
};

/*** 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:
vector<int> robtree(TreeNode* root){
if(root==NULL) return vector<int>{0,0};
vector<int> left = robtree(root->left);
vector<int> right =robtree(root->right);// 偷cur，那么就不能偷左右节点。int val1 = root->val + left[0] + right[0];// 不偷cur，那么可以偷也可以不偷左右节点，则取较大的情况int val2 = max(left[0], left[1]) + max(right[0], right[1]);return {val2, val1};
}int rob(TreeNode* root) {vector<int> result = robtree(root);return max(result[0], result[1]);}
};

 

// 版本一
class Solution {
public:int maxProfit(vector<int>& prices) {int len = prices.size();if (len == 0) return 0;vector<vector<int>> dp(len, vector<int>(2));dp[0][0] -= prices[0];dp[0][1] = 0;for (int i = 1; i < len; i++) {dp[i][0] = max(dp[i - 1][0], dp[i-1][1]-prices[i]);dp[i][1] = max(dp[i - 1][1], prices[i] + dp[i - 1][0]);}return dp[len - 1][1];}
};

// class Solution {
// public:
//     int maxProfit(vector<int>& prices) {
//         if (prices.size() == 0) return 0;
//         vector<vector<int>> dp(prices.size(), vector<int>(5, 0));
//         dp[0][1] = -prices[0];
//         dp[0][3] = -prices[0];
//         for (int i = 1; i < prices.size(); i++) {
//             //dp[i][0] = dp[i - 1][0];
//             dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] - prices[i]);
//             dp[i][2] = max(dp[i - 1][2], dp[i - 1][1] + prices[i]);
//             dp[i][3] = max(dp[i - 1][3], dp[i - 1][2] - prices[i]);
//             dp[i][4] = max(dp[i - 1][4], dp[i - 1][3] + prices[i]);
//         }
//         return dp[prices.size() - 1][4];
//     }
// };
class Solution {
public:int maxProfit(vector<int>& prices) {int k=2;if (prices.size() == 0) return 0;vector<vector<int>> dp(prices.size(), vector<int>(2 * k + 1, 0));for (int j = 1; j < 2 * k; j += 2) {dp[0][j] = -prices[0];}for (int i = 1;i < prices.size(); i++) {for (int j = 0; j < 2 * k - 1; j += 2) {dp[i][j + 1] = max(dp[i - 1][j + 1], dp[i - 1][j] - prices[i]);dp[i][j + 2] = max(dp[i - 1][j + 2], dp[i - 1][j + 1] + prices[i]);}}return dp[prices.size() - 1][2 * k];}
};

class Solution {
public:int maxProfit(int k, vector<int>& prices) {if (prices.size() == 0) return 0;vector<vector<int>> dp(prices.size(), vector<int>(2 * k + 1, 0));for (int j = 1; j < 2 * k; j += 2) {dp[0][j] = -prices[0];}for (int i = 1;i < prices.size(); i++) {for (int j = 0; j < 2 * k - 1; j += 2) {dp[i][j + 1] = max(dp[i - 1][j + 1], dp[i - 1][j] - prices[i]);dp[i][j + 2] = max(dp[i - 1][j + 2], dp[i - 1][j + 1] + prices[i]);}}return dp[prices.size() - 1][2 * k];}
};

 

 

class Solution {
public:int maxProfit(vector<int>& prices) {int n = prices.size();if (n == 0) return 0;vector<vector<int>> dp(n, vector<int>(4, 0));dp[0][0] -= prices[0]; // 持股票for (int i = 1; i < n; i++) {dp[i][0] = max(dp[i - 1][0], max(dp[i - 1][3] - prices[i], dp[i - 1][1] - prices[i]));dp[i][1] = max(dp[i - 1][1], dp[i - 1][3]);dp[i][2] = dp[i - 1][0] + prices[i];dp[i][3] = dp[i - 1][2];}return max(dp[n - 1][3], max(dp[n - 1][1], dp[n - 1][2]));}
};