动态规划--股票问题总结

股票问题总结

股票问题总的来说，可以分为大概三类，只能买卖一次、可以无限次买卖，限制买卖次数。

• 只能买卖一次
• 可以交易无限次
  • 有手续费
  • 有冷冻期
• 可以交易有限次
  • 指定次数
  • 任意次数（k次）

买卖一次

（1）dp数组

​ dp数组的含义为第i天，持有（0）和卖出（1）股票两种状态所剩的现金。

（2）初始化

​ dp[0] = -prices[0] ： 最开始买入股票是要花钱的，初始化为第一天的股票价格。

​ dp[1] = 0 : 最开始没有卖出股票，自然收益为0；

（3）状态转移方程

dp[0] = Math.max(dp[0],-prices[i-1]);  //维持买入状态，或者买入股票，由于只买入一次，就只需要-prices[i-1]
dp[1] = Math.max(dp[1],dp[0]+prices[i-1]); //维持卖出状态，或者卖出股票（卖出的前提是要先持有股票，即dp[0] + prices[i-1]）
           

（4）遍历顺序

​ 可以看到i 是 依赖i-1的状态，所以自然是从前向后进行遍历。

（5）完整代码

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

买卖多次

买卖多次和买卖一次的dp数组含义和初始化均相同，唯有状态转移方程有些许差距，

（1）状态转移方程

dp[0] = Math.max(dp[0],dp[1]-prices[i-1]);  //因为可以多次买卖，因此此时买入利益就要在上一次卖出之后所得利益（dp[1]）基础上减去成本。
dp[1] = Math.max(dp[1],dp[0]+prices[i-1]); //维持卖出状态，或者卖出股票（卖出的前提是要先持有股票，即dp[0] + prices[i-1]）
           

（2）遍历顺序

​ 可以看到i 是 依赖i-1的状态，所以自然是从前向后进行遍历。

（3）完整代码

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

买卖多次有手续费

这个题有手续费，那手续费在哪里支付呢，当然是卖出的时候，所以与上面一题唯一的区别就在于付个手续费的事儿，所以直接上完整代码。

class Solution {
  public int maxProfit(int[] prices) {
    int[] dp = new int[2];
    dp[0] = -prices[0];
    dp[1] = 0;
    for (int i = 1; i <= prices.length; i++) {
      dp[0] = Math.max(dp[0], dp[1]-prices[i - 1]);
      dp[1] = Math.max(dp[1], dp[0] + prices[i - 1] - fee); //这里要扣除一个手续费
    }
    return dp[1];
  }
}
           

买卖多次有冷冻期

冷冻期指的是每次卖出之后，要登上一天才能继续买入股票。

这里就要加入一个冷冻期状态了，因此此时每一天有三种状态**（这三种状态比较难想到，干脆多看多记记住好了）**

• 持有股票状态
• 当天卖出股票状态
• 当天是冷冻期或者冷冻期过了不是冷冻期但是没有购买股票的状态

（1）dp数组

​ dp数组的含义为：第i天持有股票所剩现金（0）、当天卖出股票所剩现金（1）、当天是冷冻期或者冷冻期过了可以买但是不买股票的状态（2）。

（2）初始化

​ dp[0] = -prices[0] dp[1] = 0 dp[2] = 0 这么初始化的原因和之前的类型一样。

（3）状态转移方程

dp[0] = Math.max(dp[0],dp[2] - prices[i-1])  //要么维持持有状态，要么就是冷冻期过了买入
dp[1] = dp[0] + prices[i-1];
dp[2] = Math.max(dp[2],dp[1]) // 要么是冷冻期，要么就不是冷冻期但是不买，保持上一次卖出的现金数
           

（4）遍历顺序

​ 可以看到i 是 依赖i-1的状态，所以自然是从前向后进行遍历。

（5）完整代码

class Solution {
  public int maxProfit(int[] prices) {
    int[] dp = new int[3];
    dp[0] = -prices[0];
    dp[1] = 0;
    dp[2] = 0;
    for (int i = 1; i <= prices.length; i++) {
      dp[0] = Math.max(dp[0], dp[2]-prices[i - 1]);
      dp[1] = dp[0] + prices[i-1];
      dp[2] = Math.max(dp[2],dp[1]);
    }
    return Math.max(dp[1],dp[2]);
  }
}
           

买卖有限次（两次）

最多做两次交易，跟只能做一次交易比起来，无非多了三种状态

• 什么也不做
• 第二次买入股票（持有）的状态 （一定是在第一次卖出之后进行）
• 第二次卖出股票的状态（在第二次买入完成之后）

（1）dp数组

​ dp数组的含义为：第i天五种状态所剩的现金。

（2）初始化

​ dp[0] = 0 dp[1] = -prices[0] dp[2] = 0 dp[3] = -prices[0] 这么初始化的原因和之前的类型一样。

（3）状态转移方程

dp[1] = Math.max(dp[1],dp[0]-prices[i-1]);
dp[2] = Math.max(dp[2],dp[1] + prices[i-1]);
dp[3] = Math.max(dp[3],dp[2]-prices[i-1]);
dp[4] = Math.max(dp[4],dp[3] + prices[i-1]);            
           

（4）遍历顺序

​ 可以看到i 是 依赖i-1的状态，所以自然是从前向后进行遍历。

（5）完整代码

class Solution {
    public int maxProfit(int[] prices) {
        //五种状态：0 不做操作，1 第一次买入，2 第一次卖出，3 第二次买入， 4 第二次卖出
        int[] dp = new int[5];
        dp[0] = 0;
        dp[1] = -prices[0];
        dp[2] = 0;
        dp[3] = -prices[0];
        dp[4] = 0;
        for(int i=1;i<=prices.length;i++){
            dp[1] = Math.max(dp[1],dp[0]-prices[i-1]);
            dp[2] = Math.max(dp[2],dp[1] + prices[i-1]);
            dp[3] = Math.max(dp[3],dp[2]-prices[i-1]);
            dp[4] = Math.max(dp[4],dp[3] + prices[i-1]);
        }
        return dp[4];
    }
}
           

买卖有限次（k次）

这个就相当于上一题的总结版，直接上代码：

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