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] };
