买卖股票的最佳时机
股票只能买卖一次，问最大的利润。
贪心解法
因为只买卖一次，很容易想到找最小的买入点，然后再找其之后的卖出点。本质上是维护左遍历右。
public int maxProfit(int[] prices) {
if (prices == null || prices.length == 0) return 0;
int low = Integer.MAX_VALUE;
int result = 0;
for (int i = 0; i < prices.length; i++) {
low = Math.min(prices[i], low);
result = Math.max(prices[i] - low, result);
}
return result;
}
动态规划
- dp[i][0] 代表第i天持有股票(不一定当天买入)所得现金
- dp[i][1] 表示第i天不持有股票所得现金
如果第i天持有股票即dp[i][0]， 那么可以由两个状态推出来
- 第i-1天就持有股票，那么就保持现状，所得现金就是昨天持有股票的所得现金 即：dp[i – 1][0]
- 第i天买入股票，所得现金就是买入今天的股票后所得现金即：-prices[i]，所以dp[i][0] = max(dp[i – 1][0], -prices[i]);
如果第i天不持有股票即dp[i][1]， 也可以由两个状态推出来
- 第i-1天就不持有股票，那么就保持现状，所得现金就是昨天不持有股票的所得现金 即：dp[i – 1][1]
- 第i天卖出股票，所得现金就是按照今天股票佳价格卖出后所得现金即：prices[i] + dp[i – 1][0]，所以dp[i][1] = max(dp[i – 1][1], prices[i] + dp[i – 1][0]);
public int maxProfit(int[] prices) {
if (prices == null || prices.length == 0) return 0;
// dp[i][0]代表第i天持有股票(不一定当天买入)的最大金额
// dp[i][1]代表第i天不持有股票的最大金额
int[][] dp = new int[prices.length][2];
dp[0][0] = -prices[0];
for (int i = 1; i < prices.length; i++) {
dp[i][0] = Math.max(dp[i - 1][0], -prices[i]);
dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] + prices[i]);
}
return dp[prices.length - 1][1];
}买卖股票的最佳时机 II
在前一题的基础上，现在不是只能买卖一次，而是可以多次买卖。
贪心解法
要想到 (第一天买，第三天卖) = (第一天买，第二天卖) + （第二天买，第三天卖），这道题就迎刃而解
class Solution {
// 把利润分解为每天为单位的维度
public int maxProfit(int[] prices) {
int result = 0;
for (int i = 1; i < prices.length; i++) {
result += Math.max(prices[i] - prices[i - 1], 0);
}
return result;
}
}
动态规划
和前一题的主要区别是，由于多次买卖，dp[i][0] 的状态发生了改变，除了维持前一天状态，在买入的时候要考虑前面买卖的利润，即 dp[i-1][1] – prices[i]
所以此时 dp[i][0] 的递推公式更新为：dp[i][0] = max(dp[i-1][0], dp[i-1][1] – prices[i])
class Solution {
public int maxProfit(int[] prices) {
if (prices == null || prices.length == 0) return 0;
// dp[i][0] 表示第i天持有股票所得最多现金
// dp[i][1] 表示第i天不持有股票所得最多现金
int[][] dp = new int[prices.length][2];
dp[0][0] = -prices[0];
dp[0][1] = 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], dp[i-1][0] + prices[i]);
}
return dp[prices.length-1][1];
}
}买卖股票的最佳时机 III
问最多买卖两次，求最大收益。
上一题是买卖一次，求最大收益，一联想，只要在上一题的基础上再多两个状态就🆗了
- dp[i][1]代表第一次持有股票后的现金
- dp[i][2]代表第一次不持有股票后的现金
- dp[i][3]代表第二次持有股票后的现金
- dp[i][4]代表第二次不持有股票后的现金
public class leetcode123 {
public int maxProfit(int[] prices) {
// dp[i][1]代表第一次持有股票后的现金
// dp[i][2]代表第一次不持有股票后的现金
// dp[i][3]代表第二次持有股票后的现金
// dp[i][4]代表第二次不持有股票后的现金
int[][] dp = new int[prices.length][5];
dp[0][1] = -prices[0];
dp[0][3] = -prices[0];
for (int i = 1; i < prices.length; i++) {
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[prices.length - 1][4];
}
}买卖股票的最佳时机 IV
问最多买卖K次，求最大收益。
上一题不就是 K = 2 的情况吗，那这题只需要简单优化一下初始化和遍历的逻辑就可以了
class Solution {
public int maxProfit(int k, int[] prices) {
// dp[i][1]代表第一次持有股票后的现金
// dp[i][2]代表第一次不持有股票后的现金
// 以此类推
int[][] dp = new int[prices.length][2 * k + 1];
// 初始化，每个持有股票的初始状态都为-prices[0]
for (int j = 1; j < dp[0].length; j += 2) {
dp[0][j] = -prices[0];
}
for (int i = 1; i < prices.length; i++) {
for (int j = 1; j < dp[0].length; j += 2) {
dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - 1] - prices[i]);
dp[i][j + 1] = Math.max(dp[i - 1][j + 1], dp[i - 1][j] + prices[i]);
}
}
return dp[prices.length - 1][2 * k];
}
}买卖股票的最佳时机含冷冻期
问多次买卖股票，每次卖出的下一天是为期一天的冷冻期，求最大收益。
乍一想只需要在 买卖股票的最佳时机 II 的基础上增加一个冷冻期的状态，但其实这样是不行的。
因为出现冷冻期之后，状态其实是比较复杂的，例如今天买入股票、今天卖出股票、今天是冷冻期，都是不能操作股票的。
所以要区分出四个状态：
- 状态一：持有股票状态（今天买入股票，或者是之前就买入了股票然后没有操作，一直持有）
- 不持有股票状态，这里就有两种卖出股票状态
- 状态二：保持卖出股票的状态（两天前就卖出了股票，度过一天冷冻期。或者是前一天就是卖出股票状态，一直没操作）
- 状态三：今天卖出股票
- 状态四：今天为冷冻期状态，但冷冻期状态不可持续，只有一天！
分析的情况放在代码中，值得注意的是，最后的返回是状态二、三、四的最大值，因为最后一天这三种状态都有可能：
class Solution {
public int maxProfit(int[] prices) {
if (prices == null || prices.length < 1) return 0;
/*
dp[i][0]持有股票(手中有/当天买)的金额
dp[i][1]保持卖出股票（冷冻期后等待买入）的金额
dp[i][2]卖出股票时的金额
dp[i][3]冷冻期的金额
*/
int[][] dp = new int[prices.length][4];
dp[0][0] = -prices[0];
for (int i = 1; i < prices.length; i++) {
// 三种情况：前一天已经持有股票/当天买入/冷冻期后一天买入
dp[i][0] = Math.max(dp[i - 1][0],
Math.max(dp[i - 1][1] - prices[i], dp[i - 1][3] - 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];
}
return Math.max(dp[prices.length - 1][1],
Math.max(dp[prices.length - 1][2], dp[prices.length - 1][3]));
}
}买卖股票的最佳时机含手续费
问多次买卖股票，每次买卖过程会多一笔手续费，求最大收益。
其实就是在 买卖股票的最佳时机 II 的基础上，增加手续费，修改一下递推公式，直接秒了。
class Solution {
public int maxProfit(int[] prices, int fee) {
if (prices.length == 0 || prices == null) return 0;
// dp[i][0] 表示第i天持有股票所得最多现金
// dp[i][1] 表示第i天不持有股票所得最多现金
int[][] dp = new int[prices.length][2];
dp[0][0] = -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], dp[i - 1][0] + prices[i] - fee);
}
return dp[prices.length - 1][1];
}
}总结
股票系列的题目，从买卖一次到买卖多次，从最多买卖两次到最多买卖k次，从冷冻期再到手续费，循序渐进，涵盖了多种状态情况，是练习动态规划的绝好系列题目。
