Day 37 动态规划
劫舍系列简单来说就是 数组上连续元素二选一，成环之后连续元素二选一，在树上连续元素二选一，所能得到的最大价值。
337. 打家劫舍 III
题目：小偷又发现了一个新的可行窃的地区。这个地区只有一个入口，我们称之为 root 。
除了 root 之外，每栋房子有且只有一个“父“房子与之相连。一番侦察之后，聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。 如果 两个直接相连的房子在同一天晚上被打劫 ，房屋将自动报警。
给定二叉树的 root 。返回 在不触动警报的情况下 ，小偷能够盗取的最高金额 。
思路：本题一定是要后序遍历，因为通过递归函数的返回值来做下一步计算。
class Solution {
public:
vector<int>helper(TreeNode* root) {
if (!root) {
return {0, 0};
}
vector<int>l = helper(root->left);
vector<int>r = helper(root->right);
// 偷当前节点
int val1 = root->val + l[0] + r[0];
// 不偷当前节点
int val2 = max(l[0], l[1]) + max(r[0], r[1]);
return {val2, val1};
}
int rob(TreeNode* root) {
vector<int>res = helper(root);
return max(res[0], res[1]);
}
};
121. 买卖股票的最佳时机
题目： 给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。
你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。
返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。
class Solution {
public:
int maxProfit(vector<int>& prices) {
vector<vector<int>>dp(prices.size(), vector<int>(2));
dp[0][0] = -prices[0];
for (int i = 1; i < prices.size(); i++) {
// 因为股票全程只能买卖一次，所以如果买入股票，那么第i天持有股票即dp[i][0]一定就是 -prices[i]
dp[i][0] = max(dp[i - 1][0], -prices[i]);
dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] + prices[i]);
}
return dp[dp.size() - 1][1];
}
};
class Solution {
public:
int maxProfit(vector<int>& prices) {
int len = prices.size();
vector<vector<int>> dp(2, vector<int>(2)); // 注意这里只开辟了一个2 * 2大小的二维数组
dp[0][0] -= prices[0];
dp[0][1] = 0;
for (int i = 1; i < len; i++) {
dp[i % 2][0] = max(dp[(i - 1) % 2][0], -prices[i]);
dp[i % 2][1] = max(dp[(i - 1) % 2][1], prices[i] + dp[(i - 1) % 2][0]);
}
return dp[(len - 1) % 2][1];
}
};
122. 买卖股票的最佳时机 II
题目： 给你一个整数数组 prices ，其中 prices[i] 表示某支股票第 i 天的价格。
在每一天，你可以决定是否购买和/或出售股票。你在任何时候 最多 只能持有 一股 股票。你也可以先购买，然后在 同一天 出售。
返回 你能获得的 最大 利润 。
class Solution {
public:
int maxProfit(vector<int>& prices) {
vector<vector<int>>dp(prices.size(), vector<int>(2));
dp[0][0] = -prices[0];
for (int i = 1; i < prices.size(); i++) {
// 因为一只股票可以买卖多次，所以当第i天买入股票的时候，所持有的现金可能有之前买卖过的利润
dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] - prices[i]);
dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] + prices[i]);
}
return dp[dp.size() - 1][1];
}
};
123. 买卖股票的最佳时机 III
题目： 给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你最多可以完成 两笔 交易。
注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
思路：一天一共就有五个状态，
- 没有操作 （其实我们也可以不设置这个状态）
- 第一次持有股票
- 第一次不持有股票
- 第二次持有股票
- 第二次不持有股票
class Solution {
public:
int maxProfit(vector<int>& prices) {
vector<vector<int>>dp(prices.size(), vector<int>(5));
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], -prices[i] + dp[i - 1][0]);
dp[i][2] = max(dp[i - 1][2], +prices[i] + dp[i - 1][1]);
dp[i][3] = max(dp[i - 1][3], -prices[i] + dp[i - 1][2]);
dp[i][4] = max(dp[i - 1][4], +prices[i] + dp[i - 1][3]);
}
return dp[dp.size() - 1][4];
}
};
188. 买卖股票的最佳时机 IV
题目： 给定一个整数数组 prices ，它的第 i 个元素 prices[i] 是一支给定的股票在第 i 天的价格，和一个整型 k 。
设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。也就是说，你最多可以买 k 次，卖 k 次。
注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
class Solution {
public:
int maxProfit(int k, vector<int>& prices) {
vector<vector<int>>dp(prices.size(), vector<int>(2 * k + 1));
for (int i = 1; i <= 2 * k; i += 2) {
dp[0][i] = -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[dp.size() - 1][2 * k];
}
};
309. 最佳买卖股票时机含冷冻期
题目： 给定一个整数数组prices，其中第 prices[i] 表示第 i 天的股票价格 。
设计一个算法计算出最大利润。在满足以下约束条件下，你可以尽可能地完成更多的交易（多次买卖一支股票）:
卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。 注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
class Solution {
public:
int maxProfit(vector<int>& prices) {
vector<vector<int>>dp(prices.size(), vector<int>(3));
dp[0][1] = -prices[0];
for (int i = 1; i < prices.size(); i++) {
dp[i][0] = max({dp[i - 1][0], dp[i - 1][1], dp[i - 1][2]});
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]);
}
return dp[dp.size() - 1][2];
}
};