代码随想录算法训练营第46期

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

dfs

/*** 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:
unordered_map<TreeNode* , int> umap; int rob(TreeNode* root) {if(root==NULL) return 0;if(root->left==NULL&&root->right==NULL){return root->val;}if(umap[root]) return umap[root];//之前算过这个点就直接返回他的值int val1=root->val;//选择当前节点的情况if(root->left) val1+=rob(root->left->left)+rob(root->left->right);//跳过root->left和root->rightif(root->right) val1+=rob(root->right->left)+rob(root->right->right);int val2=rob(root->left)+rob(root->right);//不选当前节点的情况umap[root]=max(val1,val2);return max(val1,val2);}
};

/*** 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];}
};

没有操作（其实我们也可以不设置这个状态）
第一次持有股票
第一次不持有股票
第二次持有股票
第二次不持有股票

dp[i][j]中 i表示第i天，j为 [0 - 4] 五个状态，dp[i][j]表示第i天状态j所剩最大现金。

需要注意：dp[i][1]，表示的是第i天，买入股票的状态，并不是说一定要第i天买入股票，这是很多同学容易陷入的误区。

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

以输入[1,2,3,4,5]，k=2为例。

0 表示不操作
1 第一次买入
2 第一次卖出
3 第二次买入
4 第二次卖出
.....

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

那么dp[i][0] = max(dp[i - 1][0], dp[i - 1][3] - prices[i], dp[i - 1][1] - prices[i]);

达到保持卖出股票状态（状态二）即：dp[i][1]，有两个具体操作：

dp[i][1] = max(dp[i - 1][1], dp[i - 1][3]);

达到今天就卖出股票状态（状态三），即：dp[i][2] ，只有一个操作：

昨天一定是持有股票状态（状态一），今天卖出

即：dp[i][2] = dp[i - 1][0] + prices[i];

达到冷冻期状态（状态四），即：dp[i][3]，只有一个操作：

昨天卖出了股票（状态三）

dp[i][3] = dp[i - 1][2];

状态一：持有股票状态（今天买入股票，或者是之前就买入了股票然后没有操作，一直持有）
不持有股票状态，这里就有两种卖出股票状态
- 状态二：保持卖出股票的状态（两天前就卖出了股票，度过一天冷冻期。或者是前一天就是卖出股票状态，一直没操作）
- 状态三：今天卖出股票
状态四：今天为冷冻期状态，但冷冻期状态不可持续，只有一天！
达到买入股票状态（状态一）即：dp[i][0]，有两个具体操作：
操作一：前一天就是持有股票状态（状态一），dp[i][0] = dp[i - 1][0]
操作二：今天买入了，有两种情况
- 前一天是冷冻期（状态四），dp[i - 1][3] - prices[i]
- 前一天是保持卖出股票的状态（状态二），dp[i - 1][1] - prices[i]
操作一：前一天就是状态二
操作二：前一天是冷冻期（状态四）

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

代码随想录算法训练营第46期

相关资讯

热文排行

最新新闻

推荐新闻

热搜词