【打卡】牛客网:BM82 买卖股票的最好时机(三)

发布时间:2024年01月14日

模板的:

该题与BM81的区别是,只能进行2次交易。

dp第0行:

都为0。

dp第1行:

进行第一次交易,该天持有股票的前提下,利益最大是多少。

换言之,在该天或前些天,必须买股票。需要决定第0天~第i天哪一天买入。

所以,分析第i天时

  1. 第i天不操作,即与前一天的利润(dp[1][i-1])一样,表明在第0天~第i-1天中买;
  2. 在第i天买,此时利润为买入股票的资产变化(-prices[i]),而且可以推断,第i天的股票价格是第0天~第i天的历史最低。

这与BM80的dp第1行是一样的。

dp第2行:

进行第一次交易,该天不持有股票的前提下,利益最大是多少。

所以,分析第i天时,

  1. 第i天不操作,即与前一天的利润(dp[2][i-1])一样,表明在第0天~第i-1天中,①已经买了并卖了;②没买也没卖(不存在,因为dp第1行是一定买了)。
  2. 第i天卖,那么前一天必须有股票,即前一天必须是持有股票状态。此时利润为【前一天持有股票状态的利润】加上【今天的股票价格】,即dp[1][i-1]+prices[i]。

这与BM80的dp第0行是一样的。

dp第3行:

进行第二次交易,该天持有股票的前提下,利润最大是多少。

所以,分析第i天时

  1. 第i天不操作,即与前一天的利润(dp[3][i-1])一样,表明在第0天~第i-1天中,①已经买了、卖了、买了;②买了、不操作、不操作(不存在,因为dp第3行的数据来自dp第2行,而dp第2行一定买了并卖了)。
  2. 在第i天买,那么前一天必须没有股票,即前一天必须是不持有股票状态。此时利润为【前一天不持有股票状态的利润】减去【今天的股票价格】,即dp[2][i-1]-prices[i]。

dp第4行:

进行第二次交易,该天不持有股票的前提下,利益最大是多少。

所以,分析第i天时,

  1. 第i天不操作,即与前一天的利润(dp[4][i-1])一样,表明在第0天~第i-1天中,①已经买了、卖了、买了、卖了;②不操作、不操作、不操作、不操作(不存在);③买了、卖了、不操作、不操作(不存在,理由如上)。
  2. 第i天卖,那么前一天必须有股票,即前一天必须是持有股票状态。此时利润为【前一天持有股票状态的利润】加上【今天的股票价格】,即dp[3][i-1]+prices[i]。

最后:

取0、dp第2行、dp第4行三者最优值即可。dp第2行和dp第4行表示不持有股票的最大利润;dp第1行和dp第3行表示持有股票的最大利润。所以不需要管dp第1行和dp第3行。

  1. 0表示没有进行交易的最大利润
  2. dp第2行表示完整进行一次交易(买、卖)的最大利润
  3. dp第4行表示完整进行两次交易(买、卖、买、卖)的最大利润

一些细节:

  1. BM82与BM80、BM81在初始化的不同之处
    1. BM82初始化为负无穷,从而保证dp的每一行都是有操作(买入或卖出)的。
      1. 例如,最开始出现[100,1]这样纯纯亏本的价格数组,也是必须买入100,卖出1,利润为-99。
      2. 最后return时,与0进行比较即可,从而保证如果不盈利的话不进行买卖。
    2. BM80、BM81初始化为0
      1. 如果最开始发现不盈利,是可以不操作的。例如,[100,1]的利润是0,即不买、不卖。
  2. dp的加减
    1. dp第j行表明持有股票状态的话,那么只能不操作和买入,此时是【前一天不持有股票的利润】减去【今天的价格】。
    2. dp第j行表明不持有股票状态的话,那么只能不操作和卖出,此时是【前一天持有股票的利润】加上【今天的价格】。
    3. 这是因为,对于利润而言,买入需要花钱,为利润;卖出能得到钱,为利润。

代码:

个人感觉dp第0行不要也可以。以下为我对模板的稍微改动:?

class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
     *
     * 两次交易所能获得的最大收益
     * @param prices int整型vector 股票每一天的价格
     * @return int整型
     */

    int maxProfit(vector<int>& prices) {
        // write code here
        int n = prices.size();

        vector<vector<int>> dp(4, vector<int>(n, -1000000));
        
        dp[0][0] = -prices[0];

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

        return max(dp[1][n-1], max(0, dp[3][n-1]));
    }
};

文章来源:https://blog.csdn.net/weixin_47173826/article/details/135563356
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。