当前位置：首页 > news >正文

【LeetCode 动态规划】买卖股票的最佳时机问题合集

news 来源：原创 2024/9/29 13:30:07

文章目录

- - 1. 买卖股票的最佳时机含冷冻期
  - 2. 买卖股票的最佳时机Ⅳ ---- 只允许交易 k 次🖊

1. 买卖股票的最佳时机含冷冻期

题目链接🔗
在这里插入图片描述

🍎题目思路：

在这里插入图片描述

🍎题目代码：

class Solution {
public:int maxProfit(vector<int>& prices) {int n = prices.size();vector<vector<int>> dp(n + 1, vector(3, 0));dp[0][0] = 0, dp[0][1] = -prices[0], dp[0][2] = 0;for (int i = 1; i < n; i ++){// 第 i 天结束后处于冷冻期dp[i][0] = dp[i - 1][1] + prices[i];// 处于 买入dp[i][1] = max(dp[i - 1][2] - prices[i], dp[i - 1][1]);// 处于 可交易dp[i][2] = max(dp[i - 1][0], dp[i - 1][2]);}return max(dp[n - 1][0], dp[n - 1][2]);}
};

2. 买卖股票的最佳时机Ⅳ ---- 只允许交易 k 次🖊

题目链接🔗
在这里插入图片描述

🍎题目思路：

在这里插入图片描述

🍎题目代码：

class Solution {
public:int maxProfit(int k, vector<int>& prices) {int n = prices.size();vector<vector<int>> f(n + 1, vector(k + 1, 0)); // 第 i 天结束后, 处于 买入状态vector<vector<int>> g(n + 1, vector(k + 1, 0)); // 第 i 天结束后, 处于 卖出状态// 初始化 f[][j]、g[][j]  第一天结束后, j 表示交易的次数, 第一天根本就不能完成一次交易// 为了避免对后续结果造成影响, 所以将其初始化为 -∞for (int j = 0; j <= k; j ++){f[0][j] = -0x3f3f3f3f;g[0][j] = -0x3f3f3f3f;}// 第 1 天结束后，处于买入状态f[0][0] = -prices[0];// 第 1 天结束后，处于卖出状态g[0][0] = 0;for (int i = 1; i < n; i ++){for (int j = 0; j <= k; j ++){f[i][j] = max(f[i - 1][j], g[i - 1][j] - prices[i]);// 小优化：因为 j - 1 会越界// g[i][j] = max(g[i - 1][j], f[i - 1][j - 1] + prices[i])g[i][j] = g[i - 1][j];if (j - 1 >= 0)g[i][j] = max(g[i][j], f[i - 1][j - 1] + prices[i]);}}int ans = g[n - 1][0];for (int i = 0; i <= k; i ++)ans = max(ans, g[n - 1][i]);return ans;}
};