代码随想录算法训练营day42
1.买卖股票的最佳时机IV
1.1 题目
. - 力扣(LeetCode)
1.2 题解
class Solution {
public:
int maxProfit(int k, vector<int>& prices) {
int len = prices.size();
// 定义dp数组
vector<vector<int>> dp(len, vector<int>(2 * k + 1, 0));
// 初始化
//初始化
for (int i = 0; i < 2*k; i+=2)
{
dp[0][i] = 0;
dp[0][i+1]= -prices[0];
}
// 开始遍历
for (int i = 1; i < len; i++)
{
for (int j = 0; j < 2 * k; 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[len - 1][2 * k];
}
};
2.最佳买卖股票时机含冷冻期
2.1 题目
. - 力扣(LeetCode)
2.2 题解
class Solution {
public:
int maxProfit(vector<int>& prices)
{
int len = prices.size();
//确定dp数组
vector<vector<int>> dp(len, vector<int>(4, 0));
//四个状态
//dp[i][0];// 持有股票
//dp[i][1];// 保持卖出股票
//dp[i][2];// 卖出股票
//dp[i][3];// 冷冻期
//确定递推公式
/*dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] - prices[i], dp[i - 1][3] - prices[i]);
dp[i][1] = max(dp[i - 1][3], dp[i - 1][1]);
dp[i][2] = dp[i - 1][0];
dp[i][3] = dp[i - 1][2];*/
//初始化
dp[0][0] = -prices[0];
dp[0][1] = 0;
dp[0][2] = 0;
dp[0][3] = 0;
//遍历
for (int i = 1; i < len; i++)
{
dp[i][0] = max(max(dp[i - 1][0], dp[i - 1][1] - prices[i]), dp[i - 1][3] - prices[i]);
dp[i][1] = max(dp[i - 1][3], dp[i - 1][1]);
dp[i][2] = dp[i - 1][0]+prices[i];
dp[i][3] = dp[i - 1][2];
}
return max(max(dp[len - 1][1],dp[len-1][2]),dp[len-1][3]);
}
};
3.买卖股票的最佳时机含手续费
3.1 题目
. - 力扣(LeetCode)
3.2 题解
class Solution {
public:
int maxProfit(vector<int>& prices, int fee)
{
int len = prices.size();
//确定dp数组
vector<vector<int>> dp(len, vector<int>(2, 0));
//有两个状态
//dp[i][0]//表示不持有股票
//dp[i][1]//表示持有股票
//确定递推逻辑
// dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] + prices[i]-fee);
// dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] - prices[i]);
//初始化
dp[0][0] = 0;
dp[0][1] = -prices[0];
for (int i = 1; i < len; i++)
{
dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] + prices[i] - fee);
dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] - prices[i]);
}
return max(dp[len - 1][1],dp[len-1][0]);
}
};