LeetCode刷题 - 买卖股票的最佳时机

状态： MP[i] 到第i天的最大收益 Max Profit
状态转移方程：第i天可以做两个操作
1. 买入股票 MP[i]= MP[i-1]-a[i] 就是到第i-1天的最大收益然后减去第i天的数字，因为第i天买入股票，收益就是负数
2. 卖出股票 MP[i]= MP[i-1]+a[i]

因为买之前，手里必须没有股票，卖之前，手里必须有股票，所以状态定义为一位数组，丢失很多信息，

所以状态需要定义二维 MP[i][j] : i 表示到第i天的最大收益，取值范围就是 0~(n-1) j 表示手中是否有股票，取值范围0~1 ，0 表示没有股票，1表示手里有股票所以当为0 的时候，只能买，不能买，

所以

第i天没股票的时候， MP[i][0] 分两种情况
1. 情况一第 i-1 天没股票，那么最大收益就是不动，不能买入，因为以买入，值肯定变小， = MP[i-1][0] 表示不动
2. 情况二第i-1天手里有股票，那么第i天可以卖出股票，收益就需要加上 a[i] = MP[i-1][1] + a[i] 这两个的最大值，就是第i天的最大收益，即 MP[i][0] =Math.max(MP[i-1][0],MP[i-1][1] + a[i])
第i天的时候，手里有股票的情况，MP[i][1] 同样分两种情况
1. 情况一第 i-1 天有股票，但是我不操作，那么最大收益就是 MP[i-1][1]
2. 情况二第 i-1 天手没有股票，我买入一股，那么最大收益就是 MP[i-1][0] -a[i]

这两个的最大值，就是第i天手里有股票的最大收益 MP[i][i] =Math.max(MP[i-1][1],MP[i-1][1] + a[i])

但是状态还不够，还需要一维表示交易了多少次，即 MP[i][k][j]

i 表示到第i天的最大收益，取值范围就是 0~(n-1)
j 表示手中是否有股票，取值范围0~1 ，0 表示没有股票，1表示手里有股票所以当为0 的时候，只能买，不能买，
k 表示交易了多少次，取值，从0到k

状态转移方程就需要两层循环

for(int i=0;i<n;i++){//天数的遍历
  for(int k=0;k<K;K++){//买卖次数遍历
      这里面还是分两种情况
        一 第i天的时候，手里没股票   MP[i][k][0] =Math.max( MP[i-1][k][0], MP[i-1][k-1][1]+a[i] )
          1.  第i-1天时候，手里也没有股票，那么最大收益就是 MP[i-1][k][0]
          2.  第i-1天时候，手里有股票，第i天的时候进行一次交易 -- 卖出，那么 第i-1天的时候，交易次数就是 k-1,最大收益就需要加水第i天的卖出收益，即 MP[i-1][k-1][1]+a[i],
        二  第i天的时候，手里有股票  MP[i][k][0] =Math.max( MP[i-1][k][1], MP[i-1][k-1][0]- a[i] )
          1. 第i-1天时候，手里有股票，那么最大收益就是 MP[i-1][k][1]
          2. 第i-1天时候，手里没有股票，第i天的时候进行一次交易 -- 买入，那么 第i-1天的时候，交易次数也就是 k-1,最大收益就需要减去 第i天的买入收益，即 MP[i-1][k-0][1]-a[i],
    }
}

最后的结果就是遍历交易次数k ,然后找到这个数组中第n-1天，没有股票的时候的最大值 for(int k=0;k<K;K++){//买卖次数遍历 //[n-1] 指的一共多少天 MP[n-1][k][0] 找到最大值， }