一、题目打卡
1.1 购买股票的最佳时机
题目链接:. - 力扣(LeetCode)
class Solution {
public:
int maxProfit(vector<int>& prices) {
vector<vector<int>> dp(prices.size(), vector<int>(5, 0));
/*
索引第二个的状态意义:
0. 第一次未持有,这里的第一次未持有来自于第一次持有以后卖出
1. 第一次持有
2. 第二次未持有
3. 第二次持有
4. 什么也不做 !!!这一个条件是必须要定义的,否则第一次持有的转移方向就会有问题,因为不能由第一次持有转移而来,第一次持有的话,如果卖出了,并不是第一次未持有,而是第二次未持有了
*/
dp[0][1] = - prices[0];
dp[0][3] = - prices[0];
for(int i = 1; i < prices.size();i++){
dp[i][4] = dp[i - 1][4]; // 这个本质上就是一直存着0的,以便于第一次未持有的一个前向状态的定义,或者就是一直写0也可以
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][4] - prices[i]);
dp[i][2] = max(dp[i-1][2], dp[i-1][3] + prices[i]);
dp[i][3] = max(dp[i-1][3], dp[i-1][0] - prices[i]);
}
return dp[prices.size() - 1][2];
}
};
我认为这个题目的关键在于理解这个持有和未持有,以及为什么一定需要声明一个什么都不做的状态。
对于前一个问题,其实我感觉这里说成持有和未持有不是很恰当,当然后面的时候我看的那个解析对这个说法也进行了修正,其实最正确的说法应该是第一次买入、第一次卖出......这样才能比较准确表达,而这里第一次未持有,其实就指的是第一次卖出,而且这里一定需要声明一个什么都不操作的变量,这个主要是为了存储第一次买入时候的一个前置的变量,其实就是0,所以本质上这么写也不是不行:
for(int i = 1; i < prices.size();i++){
// dp[i][4] = dp[i - 1][4]; // 这个本质上就是一直存着0的,以便于第一次未持有的一个前向状态的定义,或者就是一直写0也可以
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][2] = max(dp[i-1][2], dp[i-1][3] + prices[i]);
dp[i][3] = max(dp[i-1][3], dp[i-1][0] - prices[i]);
}
但是为了整齐或是代码美观,然后这样写的吧。
1.2 买股票的最佳时机IV
题目链接:. - 力扣(LeetCode)
class Solution {
public:
int maxProfit(int k, vector<int>& prices) {
// 无论次数的卖出,都初始化为0可以理解为当天买入卖出
vector<vector<int>> dp(prices.size(),vector<int>(2 * k + 1, 0));
/*
0. 什么也不做
1. 第一次买入
2. 第一次卖出
...
*/
for(int i = 1; i < 2 * k + 1; i = i + 2){
dp[0][i] = -prices[0];
}
for(int i = 1 ; i < prices.size();i++){
for(int j = 1; j < 2 * k + 1 ;j+=2){
dp[i][0] = dp[i-1][0];
dp[i][j] = max(dp[i-1][j], dp[i-1][j-1] - prices[i]); // 第 j 次买入 = 上一轮不动和上一轮卖出后买入
dp[i][j+1] = max(dp[i - 1][j + 1], dp[i-1][j] + prices[i]);
}
}
return dp[prices.size()-1][2*k];
// return 0;
}
};
是上一个题目的升级版,其实本质上就是多了一个循环来遍历购买卖出的所有情况,这里的每一层循环,代表的其实就是一次买入卖出的一个循环。