买卖股票的最佳时机（动态规划方法总结）

🕗 发布于 2024-10-17 18:34 动态规划算法 c++

总结一下，买卖股票系列的动态规划思想，贪心解法或者其他解法不做描述。

总结

121. 买卖股票的最佳时机只有一次交易机会，每天有两种状态：持有股票和不持有股票；

122. 买卖股票的最佳时机 II 有多次交易机会，每天有两种状态：持有股票和不持有股票；

123. 买卖股票的最佳时机 III 至多两次交易机会，每天有 2*2=4 种状态：第一次持有股票；第一次不持有股票；第二次持有股票；第二次不持有股票；

188. 买卖股票的最佳时机 IV - 力扣（LeetCode）至多 k 次交易机会，与买卖股票 3 相比，每天有 2*k=2k 种状态：第一次持有股票；第一次不持有股票；第二次持有股票；第二次不持有股票... 第 k 次持有股票；第 k 次不持有股票。

买卖股票的最佳时机 Ⅰ

题目描述：给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。

你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。

返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。

买卖股票系列的第一题，核心是只有一次交易机会。

dp 数组建立：

用两个 dp 数组来描述：

dp[i][0] 第 i 天持有股票的最大剩余现金；
dp[i][1] 第 i 天不持有股票的最大剩余现金。

重要的是理解这里的“剩余现金”是什么含义：一开始，我们持有的现金为 0，买入一支股票i后，我们持有股票的剩余现金就是-prices[i]，而在第 i+k 天卖出股票后，我们不持有股票的剩余现金就是 prices[i+k] - prices[i]，也就是交易后的利润。

dp[0][0] = -prices[0]; 因为第 0 天要持有股票，只能购入第一支股票，剩余现金为 -prices[0]；

dp[0][1] = 0; 因为第 0 天只能买入股票，无法卖出股票，因此 dp[0][1] 初始化为 0。

递推公式：

dp[i][0] = max(dp[i-1][0], -prices[i]);第 i 天持有股票，有两种情况：

- 第一种，第 i 天不买入股票，那么第 i天持有股票的剩余现金就是第 i-1天持有股票的剩余现金，即dp[i][0] = dp[i-1][0];
- 第二种，第 i 天买入股票，那么第 i天持有股票的剩余现金就是 0 减去第 i 天的股票价格，即dp[i][0] = -prices[i];
- 两者取最大值。

dp[i][1] = max(dp[i-1][1], prices[i] + dp[i-1][0]);同样有两种情况：

- 第一种，第 i 天前已经不持有股票，那么第 i天持有股票的剩余现金就是第 i-1天持有股票的剩余现金，即dp[i][1] = dp[i-1][1];
- 第二种，第 i 天当天才不持有股票，那么第 i天持有股票的剩余现金就是第 i 天的股票价格 + 第 i-1 天持有股票的最大剩余现金，即dp[i][1] = prices[i] + dp[i-1][0];
- 两者取最大值。

完整代码：

class Solution {
public:
    int maxProfit(vector<int>& prices) {

        int n = prices.size();

        // dp[i][0] 第 i 天持有股票的最大剩余现金；
        // dp[i][1] 第 i 天不持有股票的最大剩余现金。
        vector<vector<int>> dp(n, vector<int>(2, 0));
        dp[0][0] = -prices[0];
        dp[0][1] = 0;

        for (int i = 1; i < n; ++i) {
            dp[i][0] = max(dp[i - 1][0], -prices[i]);
            dp[i][1] = max(dp[i - 1][1], prices[i] + dp[i - 1][0]);
        }

        return dp[n - 1][1];
    }
};

买卖股票的最佳时机 Ⅱ

给你一个整数数组 prices ，其中 prices[i] 表示某支股票第 i 天的价格。

在每一天，你可以决定是否购买和/或出售股票。你在任何时候最多只能持有一股股票。你也可以先购买，然后在 同一天 出售。

返回 你能获得的 最大利润。

买卖股票系列的第二题，和第一题的不同之处在于，可以多次买卖股票。

dp 数组建立：

用两个 dp 数组来描述：

dp[i][0] 第 i 天持有股票的最大剩余现金；
dp[i][1] 第 i 天不持有股票的最大剩余现金。

dp[0][0] = -prices[0]; 因为第 0 天要持有股票，只能购入第一支股票，剩余现金为 -prices[0]；

dp[0][1] = 0; 因为第 0 天不管是不买股票，还是买了再卖出股票，都无法获得利润，因此 dp[0][1] 初始化为 0。

递推公式：

dp[i][0] = max(dp[i-1][0], dp[i-1][1] - prices[i]);第 i 天持有股票，有两种情况：

- 第一种，第 i 天不买入股票，那么第 i天持有股票的剩余现金就是第 i-1天持有股票的剩余现金，即dp[i][0] = dp[i-1][0];
- 第二种，第 i 天买入股票，那么第 i-1 天就不能持有股票，因为在这道题目中连续购买两支股票没有意义，只会多花钱。第 i天持有股票的剩余现金就是第 i-1 天不持有股票的最大剩余现金减去第 i 天的股票价格，即dp[i][0] = dp[i-1][1] - prices[i];
- 两者取最大值。

dp[i][1] = max(dp[i-1][1], prices[i] + dp[i-1][0]);同样有两种情况：

- 第一种，第 i 天前已经不持有股票，那么第 i天持有股票的剩余现金就是第 i-1天持有股票的剩余现金，即dp[i][1] = dp[i-1][1];
- 第二种，第 i 天当天才不持有股票，同理，第 i-1 天必须是持有股票的，没有持有股票，怎么卖出股票呢？第 i天持有股票的剩余现金就是第 i 天的股票价格 + 第 i-1 天持有股票的最大剩余现金，即dp[i][1] = prices[i] + dp[i-1][0];
- 两者取最大值。

完整代码：

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        // 动态规划
        // dp[i][0] 表示第i天持有股票的最少消耗
        // dp[i][1] 表示第i天持有股票的最大利润
        vector<vector<int>> dp(prices.size(), vector<int>(2, 0));

        dp[0][0] = -prices[0];
        dp[0][1] = 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], prices[i] + dp[i - 1][0]);
        }

        return dp[prices.size() - 1][1];
    }
};

总结：

本题和121. 买卖股票的最佳时机的代码几乎一样，唯一的区别在：

dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] - prices[i]);

因为本题的股票可以买卖多次！ 所以买入股票的时候，剩余现金可能包含之前买卖的所得利润：dp[i - 1][1]，所以 dp[i][0] 可能会等于 dp[i-1][1] - prices[i]。

想到到这一点，对这两道题理解的就比较深刻了。

买卖股票的最佳时机 Ⅲ

给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。

设计一个算法来计算你所能获取的最大利润。你最多可以完成两笔交易。

注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

这题，要求我们在购入股票时，手上不能持有其他股票，且最多只能进行两笔交易。

前两道题，同一天只有两种状态：持有股票或者不持有股票

对于这道题，同一天可以有 4 种状态：

第一次持有股票
第一次不持有股票
第二次持有股票
第二次不持有股票

那么 dp[i][j] 就表示第 i 天的 j 状态下的最大剩余现金。

dp[0][0] = -prices[0];第 0 天第一次买入；

dp[0][1] = 0;

dp[0][2] = -prices[0];第 0 天第二次买入（第一次买入后卖出，再买入，有点蛇精病，但是为了做题，只能这么买了）

dp[0][3] = 0;

递推公式：

第 i 天第一次持有股票的最大剩余金额 = max(第 i-1 天第一次持有股票的最大剩余金额, -第 i 天股票价格)
第 i 天第一次不持有股票的最大剩余金额 = max(第 i-1 天第一次不持有股票的最大剩余金额, 第 i 天股票价格 + 第 i-1 天第一次持有股票的最大剩余金额)
第 i 天第二次持有股票的最大剩余金额 = max(第 i-1 天第二次持有股票的最大剩余金额, 第 i-1 天第一次不持有股票的最大剩余金额 - 第 i 天股票价格)
第 i 天第二次不持有股票的最大剩余金额 = max(第 i-1 天第二次不持有股票的最大剩余金额, 第 i-1 天第二次持有股票的最大剩余金额 + 第 i 天股票价格)

dp[i][0] = max(dp[i - 1][0], -prices[i]);
dp[i][1] = max(dp[i - 1][1], prices[i] + dp[i - 1][0]);
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[4][4]已经包含了dp[4][2]的情况。也就是说第二次卖出的剩余现金一定是最多的。

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        // 动态规划
        // 1. 第一次持有股票
        // 2. 第一次不持有股票
        // 3. 第二次持有股票
        // 4. 第二次不持有股票
        vector<vector<int>> dp(prices.size(), vector<int>(4, 0));

        dp[0][0] = -prices[0];
        dp[0][1] = 0;
        dp[0][2] = -prices[0];
        dp[0][3] = 0;

        for (int i = 1; i < prices.size(); ++i) {
            dp[i][0] = max(dp[i - 1][0], -prices[i]);
            dp[i][1] = max(dp[i - 1][1], prices[i] + dp[i - 1][0]);
            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]);;
        }

        int result = max( dp[prices.size() - 1][1], dp[prices.size() - 1][3] );

        return result;
    }
};

买卖股票的最佳时机 Ⅳ

给你一个整数数组 prices 和一个整数 k ，其中 prices[i] 是某支给定的股票在第 i 天的价格。

设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。也就是说，你最多可以买 k 次，卖 k 次。

注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

与 123. 买卖股票的最佳时机 III 不同，这一次，我们最多可以完成 k 笔交易

那如果按照 3 的思路，我们可以用 dp[i][2 * k] 来描述第 i 天的 2k 种不同状态。

完整代码：

class Solution {
public:
    int maxProfit(int k, vector<int>& prices) {
        // 动态规划
        // 1. 第一次持有股票 dp[i][0]
        // 2. 第一次不持有股票 dp[i][1]
        // 3. 第二次持有股票 dp[i][2]
        // 4. 第二次不持有股票 dp[i][3]
        // ...
        //      k次持有 dp[i][2 * k - 2]
        //      k次不持有 dp[i][2 * k - 1]
        vector<vector<int>> dp(prices.size(), vector<int>(2 * k, 0));

        for (int i = 0; i < 2 * k; i+=2) {
            dp[0][i] = -prices[0];
        }

        for (int i = 1; i < prices.size(); ++i) {
            // 计算第一次的两个状态
            dp[i][0] = max(dp[i - 1][0], -prices[i]);
            dp[i][1] = max(dp[i - 1][1], prices[i] + dp[i - 1][0]);

            for (int j = 2; j <= k; ++j) {
                // 计算第2次到第k次的所有状态
                dp[i][2 * j - 2] = max(dp[i - 1][2 * j - 2], dp[i - 1][2 * j - 3] - prices[i]);
                dp[i][2 * j - 1] = max(dp[i - 1][2 * j - 1], dp[i - 1][2 * j - 2] + prices[i]);
            }
           
        }

        int result = dp[prices.size() - 1][2 * k - 1];

        return result;
    }
};

原文地址：https://blog.csdn.net/Teriri_/article/details/143021964

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！

上一篇：VS Code打不开？是不是“%USERPROFILE%\.vscode\extension链接到VS Code Install目录了
下一篇：搭建Elasticsearch集群

八字口诀记网线八根线序
标准网络线的颜色排序顺序
阅读更多2024-10-19
群晖前面加了雷池社区版，安装失败，然后无法识别出用户真实访问IP
有nas的相信对公网都不模式，在现在基础上传带宽能有100兆的时代，有公网代表着家里有一个小服务器，像百度网盘，优酷这种在线服务都能部署为私有化服务。但现在运营商几乎不可能提供公网ip，要么自己买个云
阅读更多2024-10-19
Game design ...and beyond
本篇文章用来记录在学习过程中所提及到的游戏设计理念。
阅读更多2024-10-19
ImageQC 相关术语解释
这些术语通常用于生物医学成像领域，用来确保图像的质量符合特定的标准，从而确保研究或诊断的准确性。解释：图像质量控制（ImageQC）使用的软件版本号，用于确保图像符合特定的质量标准。解释：指图像是否通
阅读更多2024-10-19
MBTI性格测试【职场篇】
总的来说，MBTI的目标是帮助人们了解自己的倾向和喜好，从而更好地发展个人潜力，提高工作效率和人际关系。需要注意的是，MBTI只是个人特征的一种模型，不能全面解释一个人的全部维度和特征。MBTI是一个
阅读更多2024-10-19
惊喜！又一本开源免费的大模型书来了（附PDF）
《自然语言处理：大模型理论实践》（预览版）一书以自然语言处理中语言模型为主线，涵盖了从基础理论到高级应用的全方位内容，逐步引导读者从基础的自然语言处理技术走向大模型的深度学习与实际应用。
阅读更多2024-10-19
安装和简单使用Milvus
Milvus是国产的高性能分布式向量数据库。
阅读更多2024-10-19
Linux 环境变量
environ是二级指针**environ。不用命令行参数，也能获取到环境变量，因为命令行参数默认传的就是environ。echo是个命令，最后是一个子进程，myval是本地变量不能被继承？ls创建
阅读更多2024-10-19
DLL注入的术与道：分析攻击手法与检测规则
DLL 本质上是可供其他程序使用的函数和数据的集合，可将其视为虚拟公共资源，Windows运行的任何程序都会不断地调用动态链接库，以访问各种常见函数和数据。
阅读更多2024-10-19
HTML5教程（四） - 结构标签
ul标签，ol标签，li标签，table标签，form表单，布局类标签，iframe标签，radio标签，audio标签
阅读更多2024-10-19

买卖股票的最佳时机（动态规划方法总结）

总结

买卖股票的最佳时机 Ⅰ

买卖股票的最佳时机 Ⅱ

买卖股票的最佳时机 Ⅲ

买卖股票的最佳时机 Ⅳ

相关文章