【动态规划】_leetcode刷题的各种股票问题

leetcode

1.leetcode_121.买卖股票的最佳时机

  给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。如果你最多只允许完成一笔交易（即买入和卖出一支股票），设计一个算法来计算你所能获取的最大利润。

注意你不能在买入股票前卖出股票。
示例 1:
  输入:
    [7,1,5,3,6,4]
  输出:
    5
    解释: 在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格。
示例 2:
  输入:
    [7,6,4,3,1]
  输出:
    0
    解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。

2.解题思路

方法1:

在这里插入图片描述

方法2：动态规划

dp[i][0]代表第i+1天没有持股票，dp[i][1]代表第i+1天持有股票

  • 初始化：

    • dp[0][0] = 0;       第一天没有持股，这时候相当于没有买入，故为0

      dp[0][1] = -prices[0];  第一天持股，相当于买入，这时候为-pricrs[0]

    • 状态转移方程：

    • 没有持股 =max(昨天没有持股今天维持现状 , 昨天持股，今天卖出）

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

    • 持股 = max(昨天持股今天维持现状，（之前没有交易，今天买入)）【因为只能完成一笔交易，故今天买入，则前面就相当于一直没有进行交易为利润为0】

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

3.代码

方法1：

1
2
3
4
5
6
7
8
9
10
11
12
public static int maxProfit(int[] prices) {
      int minPrice = prices[0];
      int maxProfit = 0;
      for(int i = 1;i<prices.length;i++){
          if(minPrice>prices[i]){
              minPrice = prices[i];
          }else if(maxProfit<prices[i] - minPrice){
              maxProfit = prices[i] - minPrice;
          }
      }
      return maxProfit;
  }

方法2：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
 class Solution {
    public static int maxProfit(int[] prices) {
        if(prices.length == 0)
            return 0; 
        int dp[][] = new int[prices.length][2];
        dp[0][0] = 0;
         dp[0][1] = -prices[0];
        //求第(i+1)天持股或者不持股的最大收益
        for(int i = 1;i<dp.length;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], -1 * prices[i]);
        }
        //最大利益肯定是那天没有持股时的利益
        return dp[dp.length-1][0];
    }
}

拓展1

以上题目中的“只允许完成一笔交易” 变成 “可以完成无数比交易”

同：leetcode-122:买卖股票的最佳时机 https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-ii/submissions/
动态规划：

dp[i][0]代表第i+1天没有持股票，dp[i][1]代表第i+1天持有股票

  • 初始化：
    • dp[0][0] = 0;        第一天没有持股，这时候相当于没有买入，故为0
    • dp[0][1] = -prices[0];   第一天持股，相当于买入，这时候为-prices[0]

  • 状态转移方程：

    • 没有持股 =max(昨天没有持股今天维持现状 , 昨天持股，今天卖出）

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

    • 持股 = max(昨天持股今天维持现状，（昨天没有持股，今天买入))【相对于之前，这里改变了】

      &emsp;&emsp;&emsp; `dp[i][1] = Math.max(dp[i-1][1], dp[i-1][0] - prices[i]) `

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public static int maxProfit(int[] prices) {
         if(prices.length == 0)
            return 0; 
        int dp[][] = new int[prices.length][2];
        dp[0][0] = 0;
        dp[0][1] = -prices[0];
        //求第(i+1)天持股或者不持股的最大收益
        for(int i = 1;i<dp.length;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[dp.length-1][0];
    }

拓展2：

在拓展1的基础上[可以完成无数比交易]，每次 sell 之后要等一天才能继续交易。

同：leetcode-309:最佳买卖股票时机含冷冻期 https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-with-cooldown/
动态规划：

dp[i][0]代表第i+1天没有持股票，dp[i][1]代表第i+1天持有股票

  • 初始化：
    • dp[0][0] = 0;                     //第1天没有持股，这时候相当于没有买入，故为0
    • dp[1][0] =Math.max(0,prices[1]-prices[0]); //第2天没有持股，这时候max(第一天没持股，第一天持股第二天卖出)
    • dp[0][1] = -prices[0];                //第1天持股维持，相当于买入，这时候为-prices[0]
    • dp[1][1] = Math.max(-prices[0],-prices[1]);//第2天持股，这时候max(第一天持股维持，第一天没持股第二天买入)

  • 状态转移方程：

    • 没有持股 =max(昨天没有持股今天维持现状 , (昨天持股，今天卖出))

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

    • 持股 = max(昨天持股今天维持现状，（前天没有持股，今天买入))即：第i天要买的时候，要从前天的状态进行判断

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

代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public static int maxProfit4(int[] prices) {
     if(prices.length == 0 ||prices.length == 1)
          return 0;
      int dp[][] = new int[prices.length][2];
      //初始化
      dp[0][0] = 0;
      dp[1][0] =Math.max(0,prices[1]-prices[0]);
      dp[0][1] = -prices[0];
      dp[1][1] = Math.max(-prices[0],-prices[1]);
      //动态规划
      for(int i = 2;i<dp.length;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-2][0] - prices[i]);
      }
      //最大利益肯定是那天没有持股时的利益
      return dp[dp.length-1][0];
  }
拓展3：
每次买入交易要支付手续费。

leetcode-714:买卖股票的最佳时机含手续费 https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-with-transaction-fee/
动态规划

dp[i][0]代表第i+1天没有持股票，dp[i][1]代表第i+1天持有股票

  • 初始化：

    • dp[0][0] = 0;         第一天没有持股，这时候相当于没有买入，故为0

      dp[0][1] = -prices[0] - fee;   第一天持股，相当于买入，这时候为-prices[0] - fee ,本次以买入作为交易的开始，每次买入就扣除手续费，卖出的时候就不扣除手续费了。

  • 状态转移方程：

    • 没有持股 =max(昨天没有持股今天维持现状 , 昨天持股，今天卖出）【买入扣除手续费，卖出就不扣除了，因为买卖都完成才扣一次手续费】

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

    • 持股 = max(昨天持股今天维持现状，（昨天没有持股，今天买入))

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

代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public static int maxProfit5(int[] prices,int fee) {
       if(prices.length == 0)
           return 0;
       int dp[][] = new int[prices.length][2];
       //初始化
       dp[0][0] = 0;
       dp[0][1] = -prices[0]-fee;
       //求第(i+1)天持股或者不持股的最大收益
       for(int i = 1;i<dp.length;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[dp.length-1][0];
   }
拓展4：
以上题目中的“只允许完成一笔交易” 变成 “只允许完成2笔交易”

同： https://www.nowcoder.com/questionTerminal/3e8c66829a7949d887334edaa5952c28
已调试通过
同： leetcode-123. 买卖股票的最佳时机 III :https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-iii/submissions/
动态规划

dp[i][k][0]代表第i+1天交易k次并且没有持股票，dp[i][k][1]代表第i+1天交易k次并且持有股票

  • 初始化：

    • dp[0][1][0] = 0;      //第一天，交易次数为1，没持股，相当于就没买入
    • dp[0][1][1] = -prices[0]; //第一天，交易次数为1，持股，相当于买入股票
    • dp[0][2][0] = 0;     //第一天,交易次数为2，没持股，相当于买入卖出买入卖出，没有盈利
    • dp[0][2][1] = -prices[0]; //第一天，交易次数为2，持股，相当于买入再卖出（交易1次）再买入
    • 状态转移方程：

    • 第(i+1)天交易数为2，没持股 = max(前一天交易数为2没持股维持，前一天交易数为2持股今天卖出)

      &emsp;&emsp; &emsp;`dp[i][2][0] = Math.max(dp[i-1][2][0],dp[i-1][2][1] + prices[i]);`

    • 第(i+1)天交易数为2，持股 = 前一天交易数为2持股维持，前一天交易数为1没持股今天买入[买入之前必须卖出，故之前交易数应该为1而不是为2]

      &emsp;&emsp;&emsp;`dp[i][2][1] = Math.max(dp[i-1][2][1],dp[i-1][1][0] - prices[i]);`

    • 第(i+1)天交易数为1，没持股 = max(前一天交易数为1没持股维持，前一天交易数为1持股今天卖出)[卖出之前必须买入，故交易数为1而不是0]

      &emsp;&emsp;&emsp;` dp[i][1][0] = Math.max(dp[i-1][1][0],dp[i-1][1][1] + prices[i]);`

    • 第(i+1)天交易数为1，持股 = max(前一天交易数为1持股维持，(没交易，今天买入))

      &emsp;&emsp;&emsp; ` dp[i][1][1] = Math.max(dp[i-1][1][1],-1 * prices[i]);`

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      17
      18
      19
      20
      21
      22
      23
      >     import java.util.*;
      >     public class Stock {
      >     public int maxProfit(int[] prices, int n) {
      >          if(prices.length == 0)
      >              return 0;
      >        //dp[i][k][0]代表第(i+1)天交易次数为k,没持股
      >        int dp[][][] = new int[prices.length][3][2];
      >        //初始化
      >        dp[0][1][0] = 0;  
      >        dp[0][1][1] = -prices[0];  
      >        dp[0][2][0] = 0;   
      >        dp[0][2][1] = -prices[0];
      >            //动态规划
      >        for(int i = 1;i<prices.length;i++){
      >            dp[i][2][0] = Math.max(dp[i-1][2][0],dp[i-1][2][1] + prices[i]);
      >            dp[i][2][1] = Math.max(dp[i-1][2][1],dp[i-1][1][0] - prices[i]);
      >            dp[i][1][0] = Math.max(dp[i-1][1][0],dp[i-1][1][1] + prices[i]);
      >            dp[i][1][1] = Math.max(dp[i-1][1][1],-1 * prices[i]);
      >        }
      >        return dp[prices.length-1][2][0];
      >     }
      >     }
      >

拓展5：

以上题目中的“只允许完成一笔交易” 变成 “只允许完成k笔交易”

leetcode-188: 买卖股票的最佳时机IV：https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-iv/
动态规划：

dp[i][k][0]代表第i+1天交易k次并且没有持股票，dp[i][k][1]代表第i+1天交易k次并且持有股票

  • 初始化：
    • dp[0][i][0] = 0; 【i为交易成交的笔数】即第一天,持续的买入卖出买入卖出，没收益
    • dp[0][i][1] = -prices[0]; 【i为交易成交的笔数】即第一天,持续的买入卖出买入，收益为买入的-prices[0]

  • 状态转移方程：

    • 第(i+1)天交易数为j，没持股 = max(前一天交易数为j没持股维持，前一天交易数为j持股今天卖出)

      &emsp;&emsp; &emsp;`  dp[i][j][0] = Math.max(dp[i-1][j][0], dp[i-1][j][1] + prices[i]);`

      • 第(i+1)天交易数为j，持股 = max(前一天交易数为j持股维持，前一天交易数为j没持股今天买入)

        &emsp;&emsp;&emsp; `dp[i][j][1] = Math.max(dp[i-1][j][1], dp[i-1][j-1][0] - prices[i]);`

答案超出内存限制：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public int maxProfit(int k, int[] prices) {
        if(prices.length == 0 || k==0)
            return 0;
        int dp[][][] = new int[prices.length][k+1][2];
       //初始化
       for(int i = 1;i<=k;i++)
       {
           dp[0][i][0] = 0;   //第一天,买入卖出买入卖出，没收益
           dp[0][i][1] = -prices[0]; 
       }
         //求第(i+1)天持股或者不持股的最大收益
        for(int i = 1;i<dp.length;i++){
            for(int j = k;j >= 1;j --) {
                dp[i][j][0] = Math.max(dp[i-1][j][0], dp[i-1][j][1] + prices[i]);
                dp[i][j][1] = Math.max(dp[i-1][j][1], dp[i-1][j-1][0] - prices[i]);
            }
        }
        //最大利益肯定是那天没有持股时的利益
        return dp[dp.length-1][k][0];
    }
}

有时间再想想，觉得思路应该是对的，但是这些题应该有更优的解法，动态规划时间复杂度还是有点高的。
整理自：https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock/solution/yi-ge-fang-fa-tuan-mie-6-dao-gu-piao-wen-ti-by-l-3/

本文标题:【动态规划】_leetcode刷题的各种股票问题

文章作者:qiulig

发布时间:2019-07-27, 17:14:56

最后更新:2019-07-27, 17:16:51

文章字数:3.1k

原始链接:http://blogs.qiulig.website/2019/07/【动态规划】-leetcode刷题的各种股票问题/

许可协议: "署名-非商用-相同方式共享 4.0" 转载请保留原文链接及作者。

文章目录
  1. 1. 1.leetcode_121.买卖股票的最佳时机
  2. 2. 2.解题思路
    1. 2.0.0.1. 方法1:
    2. 2.0.0.2. 方法2：动态规划
  • 3. 3.代码
    1. 3.1. 拓展1
    2. 3.2. 代码
    3. 3.3. 拓展2：
      1. 3.3.1. 代码
      2. 3.3.2. 拓展3：
      3. 3.3.3. 代码
      4. 3.3.4. 拓展4：
    4. 3.4. 拓展5：
    • | 139.6k