企业官网建设流程全解析

188.买卖股票的最佳时机IV

文章讲解/视频讲解

题目描述：

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

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

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

• 示例 1：

• 输入：k = 2, prices = [2,4,1]

• 输出：2 解释：在第 1 天 (股票价格 = 2) 的时候买入，在第 2 天 (股票价格 = 4) 的时候卖出，这笔交易所能获得利润 = 4-2 = 2。

• 示例 2：

• 输入：k = 2, prices = [3,2,6,5,0,3]

• 输出：7 解释：在第 2 天 (股票价格 = 2) 的时候买入，在第 3 天 (股票价格 = 6) 的时候卖出, 这笔交易所能获得利润 = 6-2 = 4。随后，在第 5 天 (股票价格 = 0) 的时候买入，在第 6 天 (股票价格 = 3) 的时候卖出, 这笔交易所能获得利润 = 3-0 = 3 。

提示：

• 0 <= k <= 100
• 0 <= prices.length <= 1000
• 0 <= prices[i] <= 1000

思路：

本题作为昨天III的进阶版，算得上是名副其实的hard了，昨天的III是说最多可以买卖2次，也就是限定在了可以买卖0次，1次，2次。但是本题给的是最多可以买卖k次，这就要稍微发散一下思维了。

1.确定dp数组及其下标含义：dp[i][j] ：第i天的状态为j，所剩下的最大现金是dp[i][j]

j的状态表示为：

• 0 表示不操作
• 1 第一次买入
• 2 第一次卖出
• 3 第二次买入
• 4 第二次卖出
• .....

规律其实很明显了，除了0以外，只要是j为单数就是买入，j为偶数就是卖出。因为题目规定最多交易k次，所以范围定为 2 * k + 1，也就是k（买入） + k（卖出） + 1（初始）= 2k + 1

2.确定递推公式：dp[i][j]只能通过两种情况推出来，要么前一天就已经是目前的状态了（dp[i -1][j]）。

要么前一天与今天的状态相反：比如前一天没持有，今天持有（把股票买入了），那么我们手里的现金就得减去买股票的钱，也就是dp[i -1][j -1] - price[i]。

还有可能是前一天持有，今天不持有了（股票抛掉了），那么我们手里的现金就多出来了卖出股票的钱，即dp[i -1][j -1] + price[i]。

我们很容易就能发现这两个公式唯一的差别就是加减号上，再仔细一想，只有当j是奇数（今天买入）时，我们要减，当j是偶数是（今天卖出）时，我们就加。那我们就直接用一个Math.pow( -1 , j)，计算-1的j次方，并且用计算出来的结果去乘price[i]，直接就能用一行代码搞定加减号的问题，如下：

dp[i - 1][j - 1] + Math.pow(-1, j) * prices[i]

最后我们只需要比较两种情况谁大就行了，所以递推公式完整代码如下：

dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - 1] + Math.pow(-1, j) * prices[i])

3.dp数组的初始化：毋庸置疑还是第0天要初始化，这个昨天就有一步一步递推了，j为单数时全部初始化为-price[0]（容易错写成-price[i]），偶数直接全赋值为0即可。

4.确定遍历顺序

从递归公式其实已经可以看出，一定是从前向后遍历，因为dp[i]，依靠dp[i - 1]的数值。

5.举例推导dp数组

以输入[1,2,3,4,5]，k=2为例。

最后一次卖出，一定是利润最大的，dp[prices.size() - 1][2 * k]即红色部分就是最后求解。

代码示例：

function maxProfit(k: number, prices: number[]): number { const length: number = prices.length if (length === 0) return 0 const dp: number[][] = new Array(length).fill(0).map(_ => new Array(k * 2 + 1).fill(0)) for (let i = 1; i <= k; i++) { dp[0][i * 2 - 1] = -prices[0] } for (let i = 1; i < length; i++) { for (let j = 1; j < 2 * k + 1; j++) { dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - 1] + Math.pow(-1, j) * prices[i]) } } return dp[length - 1][2 * k] };

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

文章讲解/视频讲解

题目描述：

给定一个整数数组，其中第 i 个元素代表了第 i 天的股票价格 。

设计一个算法计算出最大利润。在满足以下约束条件下，你可以尽可能地完成更多的交易（多次买卖一支股票）:

• 你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
• 卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。

示例:

• 输入: [1,2,3,0,2]
• 输出: 3
• 解释: 对应的交易状态为: [买入, 卖出, 冷冻期, 买入, 卖出]

思路：
本题比较阴间的点在于，加入了一个冷冻期那就得区分成四种状态：1.持有股票状态 2.保持卖出股票的状态 3.今天卖出股票 4.今天为冷冻期 状态2和状态4在逻辑上是可以合并的，但是放代码里就会变得极其混乱，所以还是单独拎出来了。

1.确定dp数组及其下标含义：dp[i][j]，第i天状态为j，所剩的最多现金为dp[i][j]，j的状态为：

• 0：状态一
• 1：状态二
• 2：状态三
• 3：状态四

注意这里都是持有，并非一定买入，保持买入或卖出的意思是可能前几天就买入或者卖出了，然后一直没有操作

2.确定递推公式：这是本题的主要难点，需要一个状态一个状态分析，总共四行代码：

状态一（保持买入）：要么前一天就已经买入了。要么今天买入，这又能分两种情况了，前一天是冷却期（状态四），前一天是保持卖出的状态（状态二）

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

状态二（保持卖出）：可以是前一天就已经是卖出状态了，也可以是前一天处于冷冻期（状态四）

所以dp[i][1] = max(dp[i - 1][1], dp[i - 1][3]);

状态三（今天卖股票）：只有一种情况，昨天手上有股票，今天才能有东西卖

即：dp[i][2] = dp[i - 1][0] + prices[i];

状态四（今天冷冻期）：也只有一种情况，昨天把股票卖了，今天才能处于冷冻期

dp[i][3] = dp[i - 1][2];

3.dp数组如何初始化：还是主要讨论第0天怎么初始化，首先dp[0][0]（持有股票状态）肯定等于-price[0]，这是毋庸置疑的，只能是当天买入股票。剩下的三种状态只能初始化为0，如果初始化为其他数值，第一天买入股票后，手里剩的现金数量就对不上账了，可以自己带进去试试看。

4.确定遍历顺序

从递归公式上可以看出，dp[i] 依赖于 dp[i-1]，所以是从前向后遍历。

5.举例推导dp数组

以 [1,2,3,0,2] 为例，dp数组如下：

最后结果是取 状态二，状态三，和状态四的最大值，更容易就会把状态四忘了，状态四是冷冻期，最后一天如果是冷冻期也可能是最大值。

代码示例：

function maxProfit(prices: number[]): number { const length: number = prices.length if (length === 0) return 0 const dp: number[][] = new Array(length).fill(0).map(_ => []) dp[0][0] = -prices[0] dp[0][1] = dp[0][2] = dp[0][3] = 0 for (let i = 1; i < length; i++) { dp[i][0] = Math.max(dp[i - 1][0], Math.max(dp[i - 1][3] - prices[i], dp[i - 1][1] - prices[i])) dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][3]) dp[i][2] = dp[i - 1][0] + prices[i] dp[i][3] = dp[i - 1][2] } const lastrE1: number[] = dp[length - 1] return Math.max(lastrE1[1], lastrE1[2], lastrE1[3]) };

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

文章讲解/视频讲解

题目描述：

给定一个整数数组 prices，其中第 i 个元素代表了第 i 天的股票价格 ；非负整数 fee 代表了交易股票的手续费用。

你可以无限次地完成交易，但是你每笔交易都需要付手续费。如果你已经购买了一个股票，在卖出它之前你就不能再继续购买股票了。

返回获得利润的最大值。

注意：这里的一笔交易指买入持有并卖出股票的整个过程，每笔交易你只需要为支付一次手续费。

示例 1:

• 输入: prices = [1, 3, 2, 8, 4, 9], fee = 2
• 输出: 8

解释: 能够达到的最大利润:

• 在此处买入 prices[0] = 1
• 在此处卖出 prices[3] = 8
• 在此处买入 prices[4] = 4
• 在此处卖出 prices[5] = 9
• 总利润: ((8 - 1) - 2) + ((9 - 4) - 2) = 8.

注意:

• 0 < prices.length <= 50000.
• 0 < prices[i] < 50000.
• 0 <= fee < 50000.

思路：

本题和前面两题比起来简直就是小儿科，这道题更像是“122.买卖股票的最佳时机II”的进阶版本，唯一区别就是卖股票要多一个减去手续费的操作。所以只单独讲解递推公式部分

本题dp数组的含义是：dp[i][0] 表示第i天持有股票所得最多现金。 dp[i][1] 表示第i天不持有股票所得最多现金。

那么如果第i天我们持有股票，可以从两种状态推出来，要么i -1 天就持有股票了，今天维持现状而已。要么i-1 天没持有股票，今天把股票买进来了，那现在的现金就得扣掉今天的股票价格，所以：dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] - prices[i]);

而如果第i天没持有股票，同样两种可能，可以是昨天就没持有，今天保持不变。也可以是昨天持有股票，今天卖掉了，那么现在手里的现金就能加上今天股票的卖价，但是注意还得扣掉手续费（此处是与“122.买卖股票的最佳时机II”唯一有差别的点），即dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] + prices[i] - fee);

其他代码完全一致

代码示例：

function maxProfit(prices: number[], fee: number): number { const length: number = prices.length if (length === 0) return 0 const dp: number[][] = new Array(length).fill(0).map(_ => []) dp[0][0] = -prices[0] dp[0][1] = 0 for (let i = 1; i < 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] - fee) } return dp[length - 1][1] };