今日收获：买卖股票的最佳时机，买卖股票的最佳时机Ⅱ，买卖股票的最佳时机Ⅲ

1. 买卖股票的最佳时机

题目链接：121. 买卖股票的最佳时机 - 力扣（LeetCode）

思路：

（1）二维dp数组表示第 i 天不持有股票和持有股票的状态

（2）数组初始化：第0天持有股票要花钱，不持有股票就是0

（3）遍历顺序：每一天的状态都和前一天的状态相关，所以是从左到右遍历

（4）递推公式：如果当前持有股票，则可能前一天也持有股票，也可能前一天没有股票但是当前买入股票（只能进行一次买卖所以没有资本积累，直接是-prices[i]）；如果当前没有股票，有可能前一天也没有股票或者当前持有股票再卖出。

方法：

java">class Solution {public int maxProfit(int[] prices) {int len=prices.length;// 第 i 天不持有股票和持有股票的状态int[][] dp=new int[len][2];dp[0][0]=0;dp[0][1]=-prices[0];for (int i=1;i<len;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[len-1][0];}
}

2. 买卖股票的最佳时机Ⅱ

题目链接：122. 买卖股票的最佳时机 II - 力扣（LeetCode）

思路：和只能进行一次买卖股票的思路相同，只是递推公式不一样，在买股票时允许使用前一天没有股票时的利润。

方法：

java">class Solution {public int maxProfit(int[] prices) {int len=prices.length;int[][] dp=new int[len][2];dp[0][0]=0;dp[0][1]=-prices[0];for (int i=1;i<len;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[len-1][0];}
}

3. 买卖股票的最佳时机Ⅲ

题目链接：123. 买卖股票的最佳时机 III - 力扣（LeetCode）

思路：

（1）题目中说最多有两次交易，则可以不交易，交易一次或交易两次。

（2）dp数组的状态一共有4种，分为第一次持有，第一次不持有，第二次持有和第二次不持有。（3）递推公式的推导和前面两题类似，本题除了第一次持有股票中当天买入的情况之外，其他状态都是根据前一天状态推导出来的。

方法：

java">class Solution {public int maxProfit(int[] prices) {int len=prices.length;// 4种状态，0第一次持有，1第一次不持有，2第二次持有，3第二次不持有int[][] dp=new int[len][4];dp[0][0]=-prices[0];dp[0][2]=-prices[0];  // 最多两次买入for (int i=1;i<len;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]);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]);}return dp[len-1][3];}
}