前端用动态规划玩股票II

LamHo

发布于 2022-09-26 10:44:30

2430

发布于 2022-09-26 10:44:30

文章被收录于专栏：小前端看世界

这篇文章和你去买股票没有半毛钱关系，既然你进来了，就来看看前端算法呗，嘿嘿嘿嘿！

前端没有需要刷算法？

为什么需要做算法题？大家其实都有发现在这一段2020年开始，各大公司对于前端的面试中，都不同程度的加入了算法题的测试，其中让大家最有感悟的就是字节跳动的前端面试，加入了大量的算法考验，其中不乏有很多在LeetCode上的中等以及困难题目，我也在知乎上发起了一个提问。浏览量上百万，也得到了很多的评论。

为什么字节跳动的前端面试需要那么难的算法题？

经过看了很多的评论，也明白了前端刷算法题的重要性，经过一段时间刷LeetCode，让我深有的体会的并不是这些算法在前端领域当中是否真的用到，而是算法能提高自身对于问题的理解能力，以及解决问题的能力，在刷了100多题之后，重新的自己的审视，发现自己对于同样问题的思考方式有一定的改变，所以暂且得出的结论是，刷算法对于前端开发来说，主要是提升自己的思考能力，以及对问题的分析能力。

本文概括

本文主要是讲述在LeetCode当中的股票类型题目使用动态规划的方式去解题的思路以及如何解题。

如果您已经做过，并深入理解，请阅读我的文章，看看我是否理解正确，如果你并没有做过该类题目，那么也可以阅读本文，先理解，然后关闭页面，打开LeetCode，尝试一下，挑战一下自己。

继续上一回继续说说股票相关的中等题目

最佳买卖股票时机含冷冻期 - 中等
买卖股票的最佳时机含手续费 - 中等

如果没有看上一章的，请耐心阅读完后继续看本章内容。

Lam：前端用动态规划玩股票

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

分析：

从题目上和第二题《买卖股票的最佳时机2》的要求是一样的，都是不限制次数的情况下，赚取最大利润，但是多出了一个条件，就是冷冻期。也就是说，如果今天卖出了，明天不能进行交易。像题目中所示，如果第一天以1块的价格买入股票，在第三天以3块钱卖出，那么第四天将不能以0块的价格买入。所以从题目可以直接得出，最优解应该是第一天以1块买入，第二天以2块卖出，获利1块，等待一天，在第四天以0快再次买入，第五天以2块卖出，获利2块，最终获利3块。

解题：

按照第二题的状态转移方程来进行修改：

不持股利润 = max(昨天不持股利润, 昨天持股利润 + 今天价格)
持股利润 = max(昨天持股利润, 昨天不持股利润 - 今天价格)

在第二题的时候，我们是否买入，是根据前一天的不持股利润 - 今天价格，得出是否转移状态（今天是否买入），因为本题中，有1天的冷冻期，所以我们的第二个状态的转移方程不应该与昨天的不持股利润进行计算，应该是前一天的不持股利润 - 今天价格。（只有卖出了后，相隔一天才能买入。）

最终的状态转移方程应该是：

不持股利润 = max(昨天不持股利润, 昨天持股利润 + 今天价格)
持股利润 = max(昨天持股利润, 前天不持股利润 - 今天价格)

通过上面的流程图，可以更直观的了解整个过程。

代码实现：

var maxProfit = function ( prices ) {

    if ( prices.length <= 1 ) return 0;
    if ( prices.length == 2 ) return Math.max( 0, prices[1] - prices[0] );

    const N = prices.length;

    let dp_i_0 = 0; // 卖出后的利润
    let dp_i_1 = -prices[0]; // 买入后的利润
    let pre = 0; // 前一天不持股的利润

    for ( let i = 1; i < N; i++ ) {
        
        const temp = dp_i_0; // 保留转换前的值提供给dp_i_1做计算

        // 是否卖出是根据买入后的利润+今天价钱，是否比不卖出的高来确定是否卖出
        dp_i_0 = Math.max( dp_i_0, dp_i_1 + prices[i] );

        // 是否买入是根据当前卖出后的利润-今天价钱，是否比不买入的钱多
        // 是否买入不能与上天的卖出结果进行计算，因为需要间隔一天，所以需要与上两天的卖出利润进行计算
        dp_i_1 = Math.max( dp_i_1, pre - prices[i] );

        pre = temp;
    }

    return dp_i_0;
}

有了状态转移方程，就很容易写出代码了，代码也只是仅仅添加了一个pre变量来保存每一次不持股利润在今天的状态转移之前的状态，提供给明天使用，从而保存了前一天的不持股状态。

最佳买卖股票时机含手续费

分析：

这一题其实也是基于第二题《买卖股票的最佳时机2》的变形，条件都一样，只是多了一个卖出的时候需要手续费，其实这题是非常简单的，我们只需要在不持股（卖出）的状态计算中，加上手续费，即可得出答案。

解题：

不持股利润 = max(昨天不持股利润, 昨天持股利润 + 今天价格 - 手续费)
持股利润 = max(昨天持股利润, 昨天不持股利润 - 今天价格)

代码实现：

var maxProfit = function ( prices, fee ) {

    if ( prices.length <= 1 ) return 0;
    if ( prices.length == 2 ) return Math.max( 0, prices[1] - prices[0] );

    const N = prices.length;

    let dp_i_0 = 0; // 卖出后的利润
    let dp_i_1 = -prices[0]; // 买入后的利润

    for ( let i = 1; i < N; i++ ) {

        const temp = dp_i_0; // 保留转换前的值提供给dp_i_1做计算

        // 是否卖出是根据买入后的利润+今天价钱，是否比不卖出的高来确定是否卖出
        dp_i_0 = Math.max( dp_i_0, dp_i_1 + prices[i] - fee);

        // 是否买入是根据当前卖出后的利润-今天价钱，是否比不买入的钱多
        dp_i_1 = Math.max( dp_i_1, temp - prices[i] );
    }

    return dp_i_0;
}