Java通过动态规划设计股票买卖最佳时机

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

示例：

链接：https://leetcode.cn/problems/best-time-to-buy-and-sell-stock

动态规划

因为对每一天只有两个状态，买入股票和卖出股票，因此定义 dp[][2]

1. dp[i][2] 数组表示的含义 ：

dp[i][0] 表示第 i 天买入股票能获得的最大利润，dp[i][1] 表示第一天卖出股票能获得的最大利润

2. 状态转移方程：

1. dp[i][0] = max(dp[i-1][0], -prices[i]) 

解释： 第 i 天对买入股票状态，只有两种操作，买入股票或者不买股票。因此，第 i 天能获得的最大利润为 第 i 天不买股票（dp[i-1][0]） 和 第 i 天买入股票（-prices[i]） 的利润的最大值。

1. dp[i][1] = max(dp[i-1][1], dp[i-1][0] + prices[i]) 

解释： 第 i 天对卖出股票，只有两种操作，卖出股票或者不卖出股票。因此，第 i 天能获得的最大利润为 第 i 天卖出股票 （dp[i-1][0] + prices[i]）和 第 i 天不卖出股票 的利润的最大值 （dp[i-1][1]）

3. 初始化

第 0 天买入，得到的利润为 -price[0]

第 0 天卖出，得到的利润为 0

1. dp[0][0] = -price[0] 
2. dp[0][1] = 0 

代码：

1. // 买卖股票的最佳时机 
2. public int maxProfit(int[] prices) { 
3. // dp 表示当天能获得的最大利润 
4. int[][] dp = new int[prices.length][2]; // 对每一天来说，就两个状态，一个是买入，一个是卖出 
5. dp[0][0] = -prices[0]; // 第一天买入 
6. dp[0][1] = 0; // 第一天卖出 
7. for(int i=1; i<prices.length; i++){ 
8. dp[i][0] = Math.max(dp[i-1][0], -prices[i]); 
9. dp[i][1] = Math.max(dp[i-1][1], dp[i-1][0] + prices[i]); 
10. } 
11. return dp[prices.length-1][1]; 
12. } 

变式一： 可以重复买入，卖出

1.    // 买卖股票的最佳时机2 —— 可以多次买入和卖出，但是注意每次只能持有一张股票，就是必须是 买 - 卖 - 买 - 卖 - 买 - 卖 ....这种顺序 
2. public int maxProfit2(int[] prices) { 
3. // 本题与上题的区别就在于状态转移方程不同 -- 本题可以用之前得到的利润 (即 dp[i-1][1]，上一轮卖出后剩下的钱) 再去买入，而上一题必须 0-price[i] 买入 
4. // dp[i][0] = Math.max(dp[i-1][0], dp[i-1][1]-prices[i]); ---- 买入股票能得到的最大利润状态转移方程有变化 
5. int[][] dp = new int[prices.length][2]; 
6. dp[0][0] = -prices[0]; 
7. dp[0][1] = 0; 
8. for(int i=1; i<prices.length; i++){ 
9. dp[i][0] = Math.max(dp[i-1][0], dp[i-1][1] - prices[i]); // 当天可能执行股票买入 
10. dp[i][1] = Math.max(dp[i-1][1], dp[i-1][0] + prices[i]); // 当他可能执行股票卖出 
11. } 
12. return dp[prices.length-1][1]; 
13. } 

变式二：可以执行买入卖出操作两次

1.   // 买卖股票的最佳时机3 —— 本题与上一题的区别在于，本题只能执行两次买入、卖出操作 
2. public int maxProfit3(int[] prices) { 
3. // 每次可执行的操作状态为 ，第一次买入、第一次卖出、第二次买入、第二次卖出，因此 dp 定义为 
4. int[][] dp = new int[prices.length][4]; 
5. dp[0][0] = -prices[0]; 
6. dp[0][1] = 0; 
7. dp[0][2] = -prices[0]; 
8. dp[0][3] = 0; 
9. for(int i=1; i<prices.length; i++){ 
10. dp[i][0] = Math.max(dp[i-1][0], -prices[i]); 
11. dp[i][1] = Math.max(dp[i-1][1], dp[i-1][0] + prices[i]); 
12. dp[i][2] = Math.max(dp[i-1][2], dp[i-1][1] - prices[i]); 
13. dp[i][3] = Math.max(dp[i-1][3], dp[i-1][2] + prices[i]); 
14. } 
15. return dp[prices.length-1][3]; 
16. } 

变式三：可以执行买卖操作 K 次

1. // 买卖股票的最佳时期 —— 最多进行 K 次交易 
2. public int maxProfit(int k, int[] prices) { 
3. // 就是两次交易的升级版 
4. int[][] dp = new int[prices.length][2*k+1]; // 奇数表示买入，偶数表示卖出 
5. // 初始化 
6. for(int j=1; j<2*k; j+=2){ 
7. dp[0][j] = -prices[0]; 
8. } 
9. for(int i=1; i<prices.length; i++){ 
10. for(int j=0; j<2*k-1; j+=2){ 
11. dp[i][j+1] = Math.max(dp[i-1][j+1], dp[i-1][j] - prices[i]); 
12. dp[i][j+2] = Math.max(dp[i-1][j+2], dp[i-1][j+1] + prices[i]); 
13. } 
14. } 
15. return dp[prices.length-1][2*k]; 
16. } 

变式四：含冷冻期

1.  // 买卖股票含冷冻期 
2. public int maxProfit(int[] prices) { 
3. // 一共四种状态 买入 卖出（早就卖出保存卖出态，当天卖出） 冷冻 
4. int dp[][] = new int[prices.length][4]; 
5. // 初始化 
6. dp[0][0] = -prices[0]; 
7. for(int i=1; i<prices.length; i++){ 
8. // 买入状态 —— 前一天就是买入状态 + 前一天是卖出状态今天买入了 + 前一天是冷冻状态今天买入了 
9. dp[i][0] = Math.max(dp[i-1][0], Math.max(dp[i-1][3]-prices[i], dp[i-1][2]-prices[i]) ); 
10. // 卖出态1 —— 前一天就是卖出态1 + 前一天是冷冻态 
11. dp[i][1] = Math.max(dp[i-1][1], dp[i-1][3]); 
12. // 卖出态2 —— 当天卖出了 
13. dp[i][2] = dp[i-1][0] + prices[i]; 
14. // 冷冻态 —— 前一天是卖出态2 
15. dp[i][3] = dp[i-1][2]; 
16. } 
17. return Math.max(dp[prices.length-1][1], Math.max(dp[prices.length-1][2], dp[prices.length-1][3])); 
18. } 

变式五：含手续费

1. // 买卖股票的最佳时机，含手续费 
2. public int maxProfit2(int[] prices, int fee) { 
3. int[][] dp = new int[prices.length][2]; 
4. // 初始化 
5. dp[0][0] = -prices[0] - fee; 
6. for(int i=1; i<prices.length; i++){ 
7. dp[i][0] = Math.max(dp[i-1][0], dp[i-1][1] - prices[i] - fee); 
8. dp[i][1] = Math.max(dp[i-1][1], dp[i-1][0] + prices[i]); 
9. } 
10. return dp[prices.length-1][1]; 
11. }