34. 买卖股票的最佳时机||

例题122：
给你一个整数数组 prices ，其中 prices[i] 表示某支股票第 i 天的价格。
在每一天，你可以决定是否购买和/或出售股票。你在任何时候 最多 只能持有 一股 股票。你也可以先购买，然后在 同一天 出售。

返回 你能获得的 最大 利润 。

这道题与”购买股票的最佳时机|“这道题相同，唯一的区别就是可以多次购买与卖出，但是同一时间只能持有一个股票。

动态规划

1. 确定dp数组及下标含义
   dp[i][0]表示第i天持有股票的利润：
   dp[i][1]表示第i天不持有股票的利润：
2. 确定递推公式
   dp[i][0]第i天持有股票可以由两个状态推出来：
   ① 在第i-1天就持有股票，保持原样：dp[i][0]=dp[i-1][0]；
   ② 在第i-1天不持有股票，第i天购入：dp[i][0]=dp[i-1][1]-prices[i];
   dp[i][1]第i天不持有股票可以由两个状态推出来：
   ① 第i-1天不持有股票，保持原状：dp[i][1]=dp[i-1][1]；
   ② 第i-1天持有股票，第i天卖出：dp[i][1]=dp[i-1][0]+prices[i]；
3. 初始化：数组0表示第1天
   dp[0][0]=-prices[0];
   dp[0][1]=0;
4. 确定遍历顺序
   从头到尾遍历

代码如下：

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

35. 买卖股票的最佳时机|||

例题123：
给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。

设计一个算法来计算你所能获取的最大利润。你最多可以完成 两笔 交易。

注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。


这个题比上两个题难不少，主要是最多只能买卖两次。可以不买、买一次、买两次。
所以应该有五个状态：0-4
0：无操作（可以没有）
1：第一次持有
2：第一次不持有
3：第二次持有
4：第二次不持有

需要注意：dp[i][1]，表示的是第i天，买入股票的状态，并不是说一定要第i天买入股票，这是很多同学容易陷入的误区。

对应的每一个状态也由两部分决定：
dp[i][1]表示第i天持有：① 第i-1天持有保持原状dp[i][1]=dp[i-1][1]
② 第i-1天不持有，第i天持有dp[i][1]=dp[i-1][0]-prices[i];
dp[i][2]也对应两部分：① 第i-1天不持有保持原状dp[i][2]=dp[i-1][2];
② 第i-1天持有，第i天卖出dp[i][2]=dp[i-1][1]+prices[i];
dp[i][3]：① 第i-1天持有保持原状dp[i][3]=dp[i-1][3]
② 第i-1天不持有，第i天持有dp[i][3]=dp[i-1][2]-prices[i];
dp[i][4]：① 第i-1天不持有，保持原状dp[i][4]=dp[i-1][4];
② 第i-1天持有，第i天卖出dp[i][4]=dp[i-1][3]+prices[i];

3.初始化
dp[0][0]=0
dp[0][1]=-prices[i]
dp[0][2]=0
dp[0][3]=-prices[i]
dp[0][4]=0

代码如下：

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

36. 买卖股票的最佳状态Ⅳ

例题188：
给你一个整数数组 prices 和一个整数 k ，其中 prices[i] 是某支给定的股票在第 i 天的价格。

设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。也就是说，你最多可以买 k 次，卖 k 次。

注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

这道题和上一题类似，上一题是k=2的特例。
通过上一题，可以发现，k次买卖对应着每天有（2k+1）个状态。0为无操作，偶数为不持有，奇数为持有。
第i天的dp[i][1]到dp[i][2k]的推导都对应着第i-1天购买与否两个状态。
可以发现，初始化时，如果奇数持有股票，则dp[i][奇数]=-prices[i]；如果偶数不持有，那么初始化dp[i][偶数]=0；

代码如下：

class Solution {
    public int maxProfit(int k, int[] prices) {
        int n=prices.length;
        int[][] dp=new int[n][2*k+1];
        dp[0][0]=0;
        for(int i=1;i<=2*k;i++)
        {
            if(i%2==1)
            dp[0][i]=-prices[0];
            else
            dp[0][i]=0;
        }
        for(int i=1;i<n;i++){
            for(int j=1;j<=2*k;j++){
                if(j%2==1)
                dp[i][j]=Math.max(dp[i-1][j],dp[i-1][j-1]-prices[i]);
                else
                dp[i][j]=Math.max(dp[i-1][j],dp[i-1][j-1]+prices[i]);
            }
        }
        return dp[n-1][2*k];
    }
}

37. 最佳买卖股票时机含冷冻期

例题309：
给定一个整数数组prices，其中第 prices[i] 表示第 i 天的股票价格 。​

设计一个算法计算出最大利润。在满足以下约束条件下，你可以尽可能地完成更多的交易（多次买卖一支股票）:

• 卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。
  注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

这道题比较复杂的地方在于，冷却期前不能操作股票，要分清楚第i天股票的状态。

• 状态1：持有股票
• 不持有股票，这里要细分为两种情况
  • 状态2：前一天不持有，保持这个状态（也就是说至少在前两天就卖出了股票，度过了冷冻期）
  • 状态3：前一天持有，今天卖出
• 状态4：冷冻期一天

1. 确定递推公式
   持有股票状态1：，不一定是今天买入，可能是之前就买入dp[i][0]=dp[i-1][0]
   如果是今天买入:
   ① 前一天保持卖出的状态今天买入dp[i][0]=dp[i-1][1]-prices[i]
   ② 前一天是冷冻期今天买入dp[i][0]=dp[i-1][3]-prices[i]
   所以，dp[i][0]=Math.max(dp[i-1][0],dp[i-1][1]-prices[i],dp[i-1][3]-prices[i]);
   不持有股票，分为两种状态：
   保持卖出的状态1：
   ① 前一天不持有今天不变dp[i][2]=dp[i-1][1]
   ② 前一天卖出今天冷冻期dp[i][2]=dp[i-1][3]
   所以，dp[i][1]=Math.max(dp[i-1][1],dp[i-1][3]);
   今天卖出的状态2：
   dp[i][2]=dp[i-1][0]+prices[i]
   冷冻期状态3：
   dp[i][3]=dp[i-1][2]
   2.初始化
   这里主要讨论一下第0天如何初始化。

如果是持有股票状态（状态一）那么：dp[0][0] = -prices[0]，一定是当天买入股票。

保持卖出股票状态（状态二），这里其实从 「状态二」的定义来说 ，很难明确应该初始多少，这种情况我们就看递推公式需要我们给他初始成什么数值。

如果i为1，第1天买入股票，那么递归公式中需要计算 dp[i - 1][1] - prices[i] ，即 dp[0][1] - prices[1]，那么大家感受一下 dp[0][1] （即第0天的状态二）应该初始成多少，只能初始为0。想一想如果初始为其他数值，是我们第1天买入股票后 手里还剩的现金数量是不是就不对了。

今天卖出了股票（状态三），同上分析，dp[0][2]初始化为0，dp[0][3]也初始为0。

分析了第i天可能有的四种状态分别的可能性，代码如下：

class Solution {
    public int maxProfit(int[] prices) {
        int n=prices.length;
        if(n==1 || n==0) return 0;
        int[][] dp=new int[n][4];
        dp[0][0]=-prices[0];
        dp[0][1]=0;
        dp[0][2]=0;
        dp[0][3]=0;
        for(int i=1;i<n;i++){
            dp[i][0]=Math.max(Math.max(dp[i-1][0],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(Math.max(dp[n-1][3],dp[n-1][2]),dp[n-1][1]);
    }
}

39. 买卖股票的最佳时机含手续费

例题714：
给定一个整数数组 prices，其中 prices[i]表示第 i 天的股票价格 ；整数 fee 代表了交易股票的手续费用。

你可以无限次地完成交易，但是你每笔交易都需要付手续费。如果你已经购买了一个股票，在卖出它之前你就不能再继续购买股票了。

返回获得利润的最大值。

注意：这里的一笔交易指买入持有并卖出股票的整个过程，每笔交易你只需要为支付一次手续费。

类似于无限次买卖股票那道题，每天有两种状态买和卖
dp[i][0]第i天持有股票：
如果第i-1天就持有保持状态dp[i][0]=dp[i-1][0];
如果第i-1天不持有股票，在第i天买入dp[i][0]=dp[i-1][1]-prices[i]；
dp[i][1]第i天不持有股票：
如果第i-1天不持有股票，保持状态dp[i][1]=dp[i-1][1];
如果第i-1天持有，第i天卖出dp[i][1]=dp[i-1][0]+prices[i]-fee;

初始化:
dp[0][0]=-prices[0]
dp[0][1]=0

代码如下：

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

40. 股票问题总结

股票问题分为以下几个：

1. 只能买卖一次：这个问题只需要遍历的时候更新最小买入价格和最大卖出价值即可。
2. 可以买卖无数次：第i天有买入和卖出两个状态。每个状态可以由前一天买卖与否的两个状态推出。
3. 只能买卖2次：第i天有5种状态（无操作、第一次持有、第一次不持有、第二次持有、第二次不持有），每种状态都由前一天买卖与否决定。
4. 只能买卖k次：第i天一共有2*k+1次状态，对于每种状态像上一题一样处理。注意持有和不持有的初始化
5. 卖出的后一天为冷冻期：这时第i天有四种状态（持有、当天保持不持有状态、当天卖出、冷冻期）
6. 卖出的时候有手续费：与买卖无数次相同，只不过卖出的时候需要扣除手续费。