笔记：代码随想录算法训练营day41:LeetCode121. 买卖股票的最佳时机、122.买卖股票的最佳时机II、123.买卖股票的最佳时机III
学习资料：代码随想录
121. 买卖股票的最佳时机
力扣题目链接
思路：注意题意只能买卖一次
定义：dp[i][0]表示不持有当前股票，dp[i][1]表示持有当前股票
递推公式：今天持有分之前就持有和今天才买，今天不持有分之前就不持有和今天才卖
初始化：根据递推公式，第一个数组需要初始化一下
遍历顺序：根据递推公式，从前向后
打印：略
// 定义：dp[i][0]为不持有当前股票的利润，dp[i][1]为持有当前股票的利润
// 递推公式：有四种情况：当前持有分为今天买的和之前就买了两种；当前没有分为今天卖的和之前就没有两种情况
// 初始化：第一天的就卖或不买两种情况，即持有和不持有两种情况，要初始化一下
// 遍历：从1开始
// 打印
class Solution {
public:
int maxProfit(vector<int>& prices) {
vector<vector<int>> dp(prices.size(),vector<int>(2,0));
dp[0][0] = 0;
dp[0][1] = -prices[0];
for(int i =1;i<prices.size();i++){
dp[i][0] = max(dp[i-1][0],prices[i]+dp[i-1][1]); //卖的话的减去之前买的最小价格
dp[i][1] = max(dp[i-1][1],-prices[i]); //只能卖一次
}
return dp[prices.size()-1][0];
}
};正好复习一下贪心：
class Solution {
public:
int maxProfit(vector<int>& prices) {
int result;
int low = INT_MAX;
for(int i = 0;i<prices.size();i++){
low = min(prices[i],low);
result = max(result,prices[i]-low);
}
return result;
}
};122.买卖股票的最佳时机II
力扣题目链接
思路：出奇得是，其实改动并不需要很多
在第一题的基础上，只需要在递推公式处作一点改动：在持有的情况不是第一天持有了，应该算上之前的利润
// 递推公式：今天持有：昨天就持有和昨天不持有今天买的，在这里今天买的可能是昨天卖过了
// 今天不持有：昨天不持有和今天卖的
class Solution {
public:
int maxProfit(vector<int>& prices) {
vector<vector<int>> dp(prices.size(),vector<int>(2,0));
dp[0][0] = 0;
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]+prices[i]);
dp[i][1] = max(dp[i-1][1],dp[i-1][0]-prices[i]);
}
return dp[prices.size()-1][0];
}
};复习一下贪心：
class Solution {
public:
int maxProfit(vector<int>& prices) {
int result = 0;
for(int i=0;i<prices.size()-1;i++){
result += max(prices[i+1]-prices[i],0);
}
return result;
}
};
123.买卖股票的最佳时机III
力扣题目链接
思路：
定义：dp[i][0]为没有操作；dp[i][1]为第一次持有，dp[i][2]为第一次卖出，dp[i][3]为第二次持有，dp[i][4]为第二次卖出（不持有）
递推公式：跟第一题差不多，是两个情况比较
初始化：这下要初始化五个了，其实也可以是四个，那样定义的第一个就不用了
遍历顺序：顺着走
打印：略
// 五部曲：相当于第一题的一个延伸了
// 定义：dp[i][0]为不进行操作，dp[i][1]为第一次持有，dp[i][2]为第一次不持有，dp[i][3]为第二次持有，dp[i][4]为第二次不持有
// 递推：还是四种情况：持有包括之前就持有和今天买一支，不持有包括之前就不持有和今天卖掉，那这样其实不操作的话是可以省略的
// 初始化：这里真是有意思，一支股票可以在一天内被卖来卖去的，在买之前卖了就行
// 打印
class Solution {
public:
int maxProfit(vector<int>& prices) {
vector<vector<int>> dp(prices.size(),vector<int>(5,0));
dp[0][0] = 0;
dp[0][1] = -prices[0];
dp[0][2] = 0; //当天买，当天卖
dp[0][3] = -prices[0]; //当天卖完当天还买
dp[0][4] = 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];
}
};不用dp[0][0]的写法：
class Solution {
public:
int maxProfit(vector<int>& prices) {
vector<vector<int>> dp(prices.size(),vector<int>(5,0));
//dp[0][0] = 0;
dp[0][1] = -prices[0];
dp[0][2] = 0; //当天买，当天卖
dp[0][3] = -prices[0]; //当天卖完当天还买
dp[0][4] = 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][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];
}
};