股票交易策略：动态规划与贪心算法解析

本文将探讨两个与股票交易相关的算法问题，分别是“买卖股票的最佳时机1”和“买卖股票的最佳时机Ⅱ”。这两个问题都是经典的动态规划和贪心算法的应用，目标是在给定的股票价格序列中找到能获得最大利润的策略。 ### 买卖股票的最佳时机1 **题目描述** 给定一个整数数组`prices`，表示每天的股票价格。任务是找到一个单一的交易机会，即在某一天买入并在另一天卖出股票，以获得最大的利润。 **解题思路** 这是一个基于动态规划的问题，但其实也可以用简单的遍历方法解决。我们只需要维护一个变量`pre`来存储到目前为止的最低价格，以及一个变量`res`来记录最大利润。遍历数组，如果当前价格低于`pre`，则更新`pre`；否则，如果当前价格高于`pre`，则更新最大利润`res`为`prices[i] - pre`。 **代码实现** ```cpp class Solution { public: int maxProfit(vector<int>& prices) { int n = prices.size(); if (!n) return 0; int pre = prices[0]; int res = 0; for (int i = 1; i < n; i++) { if (prices[i] < pre) pre = prices[i]; else res = max(res, prices[i] - pre); } return res; } }; ``` ### 买卖股票的最佳时机Ⅱ **题目描述** 与第一题不同的是，现在允许进行多次交易，但每次交易完成后必须卖出股票，才能进行下一次交易。目标是找到最大累计利润。 **解题思路** 对于这个问题，我们可以采用贪心算法。每次遇到一个比前一个价格高的情况，就卖出股票并积累利润。关键在于，我们不需要考虑持有状态，只需关注价格上升的情况。 **代码实现 - 贪心算法** ```cpp class Solution { public: int maxProfit(vector<int>& prices) { int n = prices.size(); if (!n) return 0; int res = 0; int pre = prices[0]; for (int i = 1; i < n; i++) { if (prices[i] > prices[i - 1]) { res += prices[i] - prices[i - 1]; } } return res; } }; // 或者，使用动态规划，虽然在这个问题中贪心已经足够 class Solution { public: int maxProfit(vector<int>& prices) { int n = prices.size(); if (!n) return 0; int dp_i_0 = 0, dp_i_1 = INT_MIN; for (int i = 1; i < n; i++) { dp_i_0 = max(dp_i_0, dp_i_1 + prices[i]); dp_i_1 = max(dp_i_1, prices[i] - prices[i - 1]); } return dp_i_0; } }; ``` 在这个动态规划版本中，状态`dp[i][0]`表示第`i`天结束时不持有股票的最大收益，`dp[i][1]`表示第`i`天结束时持有股票的最大收益。由于允许无限次交易，我们只需要关注不持有股票的状态，因此`dp[i][1]`在这里是冗余的。 总结来说，这两个问题是关于股票交易策略的经典问题，它们展示了如何运用动态规划和贪心算法来解决实际问题。在实际应用中，这些算法可以帮助我们优化决策，特别是在金融市场等需要快速响应变化的环境中。