js算法买卖股票的最佳时机入门

涉及力扣题目：
121.买卖股票的最佳时机
122.买卖股票的最佳时机II
123.买卖股票的最佳时机III
买卖股票是算法中动态规划专题里很经典的题目，它的难度包括简单到困难，但是它们的解题思路只要使用动态规划那就是一模一样没有区别，这也意味着掌握关键的算法套路很重要。

我们先来看一道入门题：

给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。
你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。
返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。

跟据前一天的收益获取今天的收益，很经典的动态规划套路。这是一道简单题对于回溯算法来解决确实是一道简单题，但是使用动态规划反而要更难这是因为，我们需要对其进行dp数组含义进行抽象这在动态规划中往往是最难的。

那我们开始进行第一也是最难的一步，创建一个二维数组，一维下标表示天数，二维下标为0就是表示要进行持有股票的操作，下标为2就是不持有股票操作，二维数组的大小就是收益。那么问题来了，假设我们知道前面天数的最大收益如何求当今收益，接下来就来到了推导公式，获取当今收益无非两种情况。1 今天啥也没做，直接就是前一天的收益dp[i-1]【0】(毕竟什么也不做也算是持有股票)或者直接买入一支新的股票0-prices[i]. 2 今天啥也不做dp[i-1][1],卖出股票dp[i-1][0]+proces[i].

对于初始化，就比较简单，直接假设当天的两种唯一情况。

dp[0] = [-prices[0], 0];

其余数组全设为0即可。

完整代码：

const maxProfit = prices => {
    const len = prices.length;
    // 创建dp数组
    const dp = new Array(len).fill([0, 0]);
    // dp数组初始化，一种是直接买股票，一种是不持有股票
    dp[0] = [-prices[0], 0];
    for (let i = 1; i < len; i++) {
        // 更新dp[i]
        dp[i] = [
            Math.max(dp[i - 1][0], -prices[i]),//持有股票的操作
            Math.max(dp[i - 1][1], prices[i] + dp[i - 1][0]),//不持有股票操作
        ];
    }
    return dp[len - 1][1];//最后减持股票肯定是最赚的，毕竟股票就是要套现的嘛
};

第二道题把题干变成了无限制次数，那么我们只需对购买股票的算法进行修改，变成前一天的收益减去购买股票的价格。

dp[i-1][0]-prices[i]

完整代码：

const maxProfit = (prices) => {
    let dp = Array.from(Array(prices.length), () => Array(2).fill(0));
    dp[0][0] = 0 - prices[0];
    dp[0][1] = 0;
    for(let i = 1; i < prices.length; i++) {
        dp[i][0] = Math.max(dp[i-1][0], dp[i-1][1] - prices[i]);
        dp[i][1] = Math.max(dp[i-1][1], dp[i-1][0] + prices[i]);
    }

    return dp[prices.length -1][1];
};

到这里大家可能会发现一种规律那就是当天的情况无非就是继承和买卖股票。其中继承就是继承前一天的财产，而买卖股票就是拿前一天的资产-+prices[i]。理解了这点接下来这道题就很简单了。

给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你最多可以完成 两笔 交易。
注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

如果可以买卖两次那么今天就会有不止两种情况了，因为我们无法知道它是购买的第一支还是第二支股票。我们可以使用最简单的方法：枚举
假设五种情况：

1. 无操作dp[i][0] = dp[i - 1][0];
2. 第一次购买dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] - prices[i]);
3. 第一次卖出dp[i][2] = Math.max(dp[i - 1][2], dp[i - 1][1] + prices[i]);
4. 第二次购买 dp[i][3] = Math.max(dp[i - 1][3], dp[i - 1][2] - prices[i]);
5. 第二次卖出 dp[i][4] = Math.max(dp[i - 1][4], dp[i - 1][3] + prices[i]);

完整代码：

const maxProfit = prices => {
    const len = prices.length;
    const dp = new Array(len).fill(0).map(x => new Array(5).fill(0));
    dp[0][1] = -prices[0];
    dp[0][3] = -prices[0];
    for (let i = 1; i < len; i++) {
        dp[i][0] = dp[i - 1][0];
        dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] - prices[i]);
        dp[i][2] = Math.max(dp[i - 1][2], dp[i - 1][1] + prices[i]);
        dp[i][3] = Math.max(dp[i - 1][3], dp[i - 1][2] - prices[i]);
        dp[i][4] = Math.max(dp[i - 1][4], dp[i - 1][3] + prices[i]);
    }
    return dp[len - 1][4];
};