买股票的最佳时期，是一道经典的动态规划题目，在leetcode中有很多题目。今天通过一个通用的dp推导公式解决所有的股票问题，具体解决动态规划的问题的方法步骤可以参考本人的上一篇博客。
题目：
给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。设计一个算法来计算你所能获取的最大利润。你最多可以完成 k比 交易。
注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
假设k=2
示例 1:
输入：prices = [3,3,5,0,0,3,1,4]
输出：6
解释：在第 4 天（股票价格 = 0）的时候买入，在第 6 天（股票价格 = 3）的时候卖出，这笔交易所能获得利润 = 3-0 = 3 。
随后，在第 7 天（股票价格 = 1）的时候买入，在第 8 天 （股票价格 = 4）的时候卖出，这笔交易所能获得利润 = 4-1 = 3 。
示例 2：
输入：prices = [1,2,3,4,5]
输出：4
解释：在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。
注意你不能在第 1 天和第 2 天接连购买股票，之后再将它们卖出。
因为这样属于同时参与了多笔交易，你必须在再次购买前出售掉之前的股票。
下面解析推导公式：
首先确定每天对股票操作的选择种类：
- 买入 buy
- 卖出 sell
- 保持不动 reset
其次确定状态有哪里：
- 天数 n
- k 表示当前至多操作股票次数
- 当前的股票状态【0-未持有股票 1- 持有股票】
假设dp[ i ][ k ][ 0] 表示第 i 天不持有股票，至多操作k 次股票（1次操作股票代表买入和卖出）的最大收益，那么要最终要求解的值为dp[n-1] [k] [0] 。
dp [i][k][0] = max( dp[i-1][k][0] , dp[i-1][k-1][1] + price[i])
解释：dp[i][k][0]表示当前不持有股票，那么不持有股票有2种情况：
1. 前一天不持有股票 ，当天不操作。即 dp[i-1][k][0]
2. 前一天持有股票的情况下，将股票卖了。即 dp[i-1][k][1] + price[i] ( 这里我们在买入股票是对k 进行加一，卖出就不在进行加一了)
dp[i][k][1] = max(dp[i-1][k][1], dp[i-1][k][0] - price[i])
解释：dp[i][k][1]表示当前持有股票，那么持有股票有2中情况：
1. 前一天持有股票的情况下，当天不操作。即：dp[i-1][k][1]
2. 前一天不持有股票的情况下，当天买入。即：dp[i-1][k-1][0] - price[i]（买入的情况下要对 k进行加一，由于当前值是k ,所以前一天就是k-1)
下面确定base case:
dp[i][0][1] = 负无穷 （表示不存在）
解释： 操作0次的情况下，持有股票，这种情况明显不存在
dp[i][0][0] = 0
解释： 操作0次的情况下，不持有股票，当前收益肯定是0
dp[0][k][0] = 0 第一天不持有股票的收益为0。
dp[0][k][1] = -price[0] 第一天持有股票的收益是-price[0]。k表示至少操作股票次数, 因此 k>=1
总结：
dp公式：
dp[i][k][0] = Max(dp[i-1][k][0], dp[i-1][k][1] + price[i])
dp[i][k][1] = Max(dp[i-1][k][1], dp[i-1][k-1][0] - price[i])
base case:
dp[i][0][0] = 0;
dp[i][0][1] = -infinity
买股票的基本dp公式已经写完，下面来看具体的问题。
- 第一题：
给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。
如果你最多只允许完成一笔交易（即买入和卖出一支股票一次），设计一个算法来计算你所能获取的最大利润。
注意：你不能在买入股票前卖出股票。
示例 1:
输入: [7,1,5,3,6,4]
输出: 5
解释: 在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock
解析：
从题目可以看出，该题 k = 1，只允许买入和卖出1次
套用公式：
dp[i][1][0] = max (dp[i-1][1][0], dp[i-1][1][1] + price[i])
dp[i][1][1] = max (dp[i-1][1][1], dp[i-1][0][0] - price[i])
这里我们可以简化下公式，将k去掉：
根据：上面通用的base case可知， dp[i-1][0][0] = 0
因此公式可以简化为：
dp[i][1][0] = max (dp[i-1][1][0], dp[i-1][1][1] + price[i])
dp[i][1][1] = max (dp[i-1][1][1], - price[i])
而由于公式中k都是等于1，因此可以将k去掉，最终简化后的公式为：
dp[i][0] = max(dp[i-1][0], dp[i-1][1] + price[i])
dp[i][1] = max(dp[i-1][1], -price[i])
然后就是base case了：
dp[0][0] = 0 第1天不持有股票的情况
dp[0][1]= - price[0] 第1天持有股票的情况
现在可以很容易对该题进行求解了：
public int maxProfit(int[] prices) {
int [][] dp = new int[prices.length][2];
dp[0][1] = - prices[0];
for(int 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], -prices[i]);
}
return dp[prices.length - 1][0];
}
当前的方法还能进行优化，可以将空间复杂度O(n)，优化为O(1)。
public int maxProfit(int[] prices) {
int i_0 = 0;
int i_1 = -prices[0];
for(int i = 1; i < prices.length; i++) {
i_0 = Math.max(i_0, i_1 + prices[i]);
i_1 = Math.max(i_1, -prices[i]);
}
return i_0;
}
- 第二题
给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。
注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-ii
解析：
dp公式：
dp[i][k][0] = Max(dp[i-1][k][0], dp[i-1][k][1] + price[i])
dp[i][k][1] = Max(dp[i-1][k][1], dp[i-1][k-1][0] - price[i])
由于k不限制大小，因此可以直接去掉公式中的k的值了
dp[i][0] = max(dp[i-1][0], dp[i-1][1] + price[i]
dp[i][1] = max(dp[i-1][1], dp[i-1][0] - price[i]
因此结果为：
public int maxProfit(int[] prices) {
int i_0 = 0;
int i_1 = -prices[0];
for(int i = 1; i < prices.length; i++) {
int tmp = i_0;
i_0 = Math.max(i_0, i_1 + prices[i]);
i_1 = Math.max(i_1, tmp - prices[i]);
}
return i_0;
}
- 第三题
给定一个整数数组 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.
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-with-transaction-fee
解析：
该题和第二题的区别，是多了一个手续费，dp公式如下：
dp[i][0] = max(dp[i-1][0], dp[i-1][1] + price[i])
dp[i][1] = max(dp[i-1][1], dp[i-1][0] - price[i] - fee) //买入是需要扣除手续费
base case:
dp[0][0] = 0;
dp[0][1] = -price[i] - fee
因此优化后的代码如下：
public int maxProfit(int[] prices, int fee) {
int i_0 = 0;
int i_1 = -prices[0] - fee; //首次买入扣除手续费
for(int i = 1; i < prices.length; i++) {
int tmp = i_0;
i_0 = Math.max(i_0, i_1 + prices[i]);
i_1 = Math.max(i_1, tmp - prices[i] - fee);
}
return i_0;
}
- 第四题
给定一个整数数组，其中第 i 个元素代表了第 i 天的股票价格 。
设计一个算法计算出最大利润。在满足以下约束条件下，你可以尽可能地完成更多的交易（多次买卖一支股票）:
你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-with-cooldown
解析：
该题与第二题相比多了一个冷冻期，也就是说卖出后，第二天 不能买入。因此只需要修改下dp公式：
第二题dp 公式：
dp[i][0] = max(dp[i-1][0], dp[i-1][1] + price[i]
dp[i][1] = max(dp[i-1][1], dp[i-1][0] - price[i]
由于卖出后第二天不能买入，因此
dp[i][0] = max(dp[i-1][0], dp[i-1][1] + price[i]）
dp[i][1] = max(dp[i][1], dp[i-2][0] - price[i]) //第i天要买股票，需要i-2天卖股票后（i-2天之后不在持有股票），才能买。
base case:
dp[0][0] = 0;
dp[0][1] = -price[i]
dp[-1][0] = 0 表示：开市前一天未持有股票，因此值为0
public int maxProfit(int[] prices) {
if(prices.length == 0) {
return 0;
}
int dp_pre_0 = 0; //记录dp[i-2][0]
int dp_i_0 = 0;
int dp_i_1 = -prices[0];
for(int i = 1; i < prices.length; i++) {
int tmp = dp_i_0;
dp_i_0 = Math.max(dp_i_0, dp_i_1 + prices[i]);
dp_i_1 = Math.max(dp_i_1, dp_pre_0 - prices[i]);
dp_pre_0 = tmp;
}
return dp_i_0;
}
- 第五题
给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。设计一个算法来计算你所能获取的最大利润。你最多可以完成 两笔 交易。
注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-iii
解析：
public int maxProfit(int[] prices) {
int[][][] dp = new int[prices.length][3][2];
//base case
for(int i = 0; i < prices.length; i++) {
dp[i][0][1] = Integer.MIN_VALUE;
dp[i][0][0] = 0;
}
for (int k = 1; k < 3; k++) {
dp[0][k][1] = -prices[0];
dp[0][k][0] = 0;
}
//dp公式
for(int i = 1; i < prices.length; i++) {
for(int k = 1; k < 3; k++) {
dp[i][k][0] = Math.max(dp[i-1][k][0], dp[i-1][k][1] + prices[i]);
dp[i][k][1] = Math.max(dp[i-1][k][1], dp[i-1][k-1][0] - prices[i]);
}
}
return dp[prices.length-1][2][0];
}
- 第六题
给定一个整数数组 prices ，它的第 i 个元素 prices[i] 是一支给定的股票在第 i 天的价格。设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。
注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-iv
解析：直接套用公式
public int maxProfit(int k, int[] prices) {
if (prices.length == 0) {
return 0;
}
if (k > prices.length / 2) { // 相当于k不限制次数
return maxProfit(prices);
}
int[][][] dp = new int[prices.length][k + 1][2];
for (int i = 0; i < prices.length; i++) {
dp[i][0][1] = Integer.MIN_VALUE;
dp[i][0][0] = 0;
}
for (int j = 1; j <= k; j++) {
dp[0][j][1] = -prices[0];
dp[0][j][0] = 0;
}
for (int i = 1; i < prices.length; i++) {
for (int j = 1; j <= k; j++) {
dp[i][j][0] = Math.max(dp[i - 1][j][0], dp[i - 1][j][1] + prices[i]);
dp[i][j][1] = Math.max(dp[i - 1][j][1], dp[i - 1][j - 1][0] - prices[i]);
}
}
return dp[prices.length - 1][k][0];
}
public int maxProfit(int[] prices) {
int i_0 = 0;
int i_1 = -prices[0];
for (int i = 1; i < prices.length; i++) {
int tmp = i_0;
i_0 = Math.max(i_0, i_1 + prices[i]);
i_1 = Math.max(i_1, tmp - prices[i]);
}
return i_0;
}
