力扣刷题-动态规划算法5：股票买卖问题_买卖股票交易 力扣

1. 问题汇总

2. 题目汇总

2.1. 题目一：121.买卖股票的最佳时机（一笔交易）

1. 题目描述

2. 思路解答
   1）用贪心的方法进行求解
   （1）：记录两个元素，一个是从第零天到第i天开始，股票价格的最低值
   （2）：在第 i 时刻如果卖出的话，能够盈利的最大值。
   2）用动态规划方法进行求解：dp拥有两种状态，持有或者未持有
   （1）：持有状态：dp[ i ][ 0 ]= Math.max( dp[ i-1 ][ 0 ] ， -prices[ i ]); //注意：由于只交易一次，故持有的话，不是和上一个时刻一致，就是在这个时刻买入
   （2）：未持有状态：dp[ i ][ 1 ]= Math.max( dp[ i-1 ][ 1 ] ，dp[ i-1 ][ 0 ]+prices[ i ]);
3. 代码详解

	//1）贪心题解
    public int maxProfit(int[] prices) {

        //1)遍历
        int min=prices[0];   //找出i索引之前最小值
        int max=0;       //找出i索引之前dp的最大值
        for(int i=1;i<prices.length;i++){
            min=Math.min(prices[i],min);
            max=Math.max(prices[i]-min,max);
        }
        
        return max;
    }```

```java
	//2）动态规划题解
    public int maxProfit(int[] prices) {
        //动规分为两种状态
        //dp[i][0]:在i时刻，持有股票，手上的钱最大值，用最低的钱买到股票
        //dp[i][1]:在i时刻，不持有股票，手上的钱最大值

        //0）特殊情况
        if(prices.length==1) return 0;

        //1)新建并初始化dp
        int[][] dp=new int[prices.length][2];
        dp[0][0]=-prices[0];  //持有股票，即在该时刻买入
        dp[0][1]=0;           //不持有，即前面不可能有买入，故为0

        //2）遍历
        for(int i=1;i<prices.length;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]);//要么是之前就卖出了，不持有；要么就是现在才卖出的
        }

        //3）输出
        return dp[prices.length-1][1];

    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

2.2. 题目二：122.买卖股票的最佳时机II（多笔交易）

1. 题目描述
   

2. 解题思路
   1）贪心思想
   （1）：由于可以交易多次，并且没有手续费，故只有后者比前者大，就可以进行一次买入卖出操作
   （2）：可以从i=1开始，如果prices[i] -prices[i-1],那么可以在i 时刻进行卖出操作
   2）动态规划思想（为后面的题目做铺垫）：骨片存在两种状态（持有和不持有）
   （1）：持有状态：dp[ i ][ 0 ]= Math.max( dp[ i-1 ][ 0 ] ，dp[ i -1][ 1 ] -prices[ i ]); //注意：由于存在多次交易，故为未持有装填减去prices[ i ]，这也是和题目一的区别。
   （2）：未持有状态：dp[ i ][ 1 ]= Math.max( dp[ i-1 ][ 1 ] ，dp[ i-1 ][ 0 ]+prices[ i ]);## 2.3. 题目三：121.买卖股票的最佳时机

3. 代码详解

	//1）贪心思想
	    public int maxProfit(int[] prices) {
        //1）得到一个后者减去前者的数组
        int[] cha=new int[prices.length];
        int result=0;
        for(int i=1;i<prices.length;i++){
            cha[i]=prices[i]-prices[i-1];
            if(cha[i]>=0) result+=cha[i];
        }
        //System.out.println(Arrays.toString(cha));
        return  result;
    }
1
2
3
4
5
6
7
8
9
10
11
12

	//2）动态规划思想
    public int maxProfit(int[] prices) {
        //动态规划方法：和之前的只差在持有股票上面

        //0）特殊情况
        if(prices.length==1) return 0;

        //1)dp数组的定义和初始化
        int [][] dp=new int[prices.length][2];
        dp[0][0]=-prices[0];  //持有股票时
        dp[0][1]=0;           //不持有股票时

        //2）遍历
        for(int i=1;i<prices.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]);   //和之前一样
        }

        //3）输出
        return dp[prices.length-1][1];  //不持有股票，钱最多
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

2.3. 题目三：123.买卖股票的最佳时机III（完成两笔交易）

1. 题目描述
   

2. 解题思路
   1）首先和股票问题二很像，只是有两笔交易故有五种状态
   （0）：状态一：dp[i][0]:无交易状态
   （1）：状态二：dp[i][1]:第一笔交易，持有股票 ：比较【dp[i-1][1]，dp[i-1][0]-prices[i ] 】
   （2）：状态二：dp[i][2]:第一笔交易，不持有股票：比较【dp[i-1][2]，dp[i-1][1]+prices[i ] 】
   （3）：状态二：dp[i][3]:第二笔交易，持有股票：比较【dp[i-1][3]，dp[i-1][2]-prices[i ] 】
   （4）：状态二：dp[i][4]:第二笔交易，不持有股票：比较【dp[i-1][4]，dp[i-1][3]+prices[i ] 】
   2）针对五种状态进行迭代，然后最大的状态为dp[i][4]。

3. 代码详解

	//1）普通模式
	    public int maxProfit(int[] prices) {
        //延续上一题股票买卖的思路
        //1）dp[i][0]:不操作
        //2）dp[i][1]:第一次买入
        //3）dp[i][2]:第一次卖出
        //4）dp[i][3]:第二次买入
        //5）dp[i][4]:第一次卖出

        //1）特殊情况
        if(prices.length==1) return 0;

        //2)dp的初始化与定义
        int[][] dp=new int [prices.length][5];
        //for(int i=1;i<5;i++) dp[0][i]=-prices[0];
        dp[0][1]=-prices[0];
        dp[0][3]=-prices[0];
        //3)遍历
        for(int i=1;i<prices.length;i++){
            dp[i][0]=dp[i-1][0];                                //不操作，就一直保持零

            dp[i][1]=Math.max(dp[i-1][0]-prices[i],dp[i-1][1]); //第一次买入的最低价
            dp[i][2]=Math.max(dp[i-1][1]+prices[i],dp[i-1][2]); //第一次卖出的最高价
            dp[i][3]=Math.max(dp[i-1][2]-prices[i],dp[i-1][3]); //第二次买入的最低价 
            dp[i][4]=Math.max(dp[i-1][3]+prices[i],dp[i-1][4]); //第二次卖出的最低价   
        }

        //4)输出
        return dp[prices.length-1][4];
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

	//采用for循环的模式，方便后面修改为多次股票交易
	    public int maxProfit(int[] prices) {
        //延续上一题股票买卖的思路
        //1）dp[i][0]:不操作
        //2）dp[i][1]:第一次买入
        //3）dp[i][2]:第一次卖出
        //4）dp[i][3]:第二次买入
        //5）dp[i][4]:第一次卖出

        //1）特殊情况
        if(prices.length==1) return 0;

        //2)dp的初始化与定义
        int[][] dp=new int [prices.length][5];
        for(int i=1;i<5;i+=2) dp[0][i]=-prices[0];

        //3)遍历
        for(int i=1;i<prices.length;i++){
            dp[i][0]=dp[i-1][0];                                //不操作，就一直保持零
            for(int j=1;j<5;j++){
                if(j%2==1){  //奇数买入
                    dp[i][j]=Math.max(dp[i-1][j-1]-prices[i],dp[i-1][j]);
                }else{       //偶数买入
                    dp[i][j]=Math.max(dp[i-1][j-1]+prices[i],dp[i-1][j]);
                }
            }
        }
        //4)输出
        return dp[prices.length-1][4];
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

2.4. 题目四：188. 买卖股票的最佳时机 IV（交易k笔）

1. 题目描述
   

2. 解题思路
   1）这一题和上一题一模一样，只是需要修改一下k值
   2）核心思路是：记录每一次交易的转态，如果有K笔交易，故需要有2*K+1种状态。

3. 代码详解

    public int maxProfit(int k, int[] prices) {
        //1）特殊情况
        if(prices.length<=1 ||k==0)  return 0;

        //2)dp的定义和初始化
        int[][] dp=new int[prices.length][2*k+1];
        for(int i=1;i<2*k+1;i+=2) dp[0][i]=-prices[0];

        //3)迭代递归
        for(int i=1;i<prices.length;i++){
            for(int j=1;j<2*k+1;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]); 
                }
            }
        }

        //4)输出
        return dp[prices.length-1][2*k];

    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

2.5. 题目五：309. 最佳买卖股票时机含冷冻期（多笔交易，有冷冻期）

1. 题目描述

2. 解题思路
   1）因为有冷冻期，故代码需要在题目2基础上添加有冷冻期的状态
   （1）：状态一：dp[i[0]：持有股票：其他三种情况之后均可以持有
   （2）：状态二：dp[i[1]：不持有股票，在这个时刻卖出的：只有一种情况
   （3）：状态三：dp[i[2]：不持有股票，冷冻期：只有一种情况，前面刚卖出
   （4）：状态三：dp[i[2]：不持有股票，度过了冷冻期：可以有两种情况：前面是冷冻期和不是不持股不是冷冻期
   2）根据既定的四种状态，进行更新，最大取值有三种情况：2,3，4，都可能是最大的。
3. 代码详解

    public int maxProfit(int[] prices) {
        //0)特殊情况
        if(prices.length==1)  return 0;

        //1)dp数组的定义
        int[][] dp=new int[prices.length][4];
        dp[0][0]=-prices[0];   //持有股票,购买没有操作；或者今天购买的股票（前一天为持有状态，前一天为冷冻期，前一天为过了冷冻期）
        dp[0][1]=0;            //不持有股票,今天卖出的（前一天为持有股票状态）
        dp[0][2]=0;            //不持有股票,冷冻期（前一天为当天卖出股票）
        dp[0][3]=0;            //不持有股票,不是今天卖出的，度过了冷冻期(前一天为冷冻期，前一天为度过冷冻期)

        //3）迭代遍历
        for(int i=1;i<prices.length;i++){
            dp[i][0]=Math.max(dp[i-1][0],Math.max(dp[i-1][2]-prices[i],dp[i-1][3]-prices[i]));//三种情况
            dp[i][1]=dp[i-1][0]+prices[i];  //一种情况
            dp[i][2]=dp[i-1][1];            //一种情况
            dp[i][3]=Math.max(dp[i-1][1], dp[i-1][3]);  //两种情况
        }

        //4)结果
        //结果再三个地方都可以，只要是处于不持有股票状态
        return Math.max(dp[prices.length-1][1],Math.max(dp[prices.length-1][2],dp[prices.length-1][3]));
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

2.6. 题目六：714. 买卖股票的最佳时机含手续费（多笔交易，增加手续费）

1. 题目描述

2. 解题思路
   1）在题目二的基础上进行修改。只是需要在卖出的时候，增加手续费即可。
3. 代码展示

    public int maxProfit(int[] prices, int fee) {
        //动态规划算法，维持两种状态即可

        //1）特殊
        int size=prices.length;
        if(size==1) return 0;

        //2)dp的定义与初始化
        int[][] dp=new int[size][2];
        dp[0][0]=-prices[0];  //在这个时刻如果是持有股票
        dp[0][1]=0;           //在这个时刻如果是不持有股票

        //3）遍历和迭代
        for(int i=1;i<size;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);  //和题目二不一样的地方
        }

        //4）输出
        return dp[size-1][1];
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

3. 股票买卖总结

1. 题目一：121.买卖股票的最佳时机（一笔交易）：一维数组
2. 题目二：122.买卖股票的最佳时机II（多笔交易）：二维数组，两种状态
3. 题目三：123.买卖股票的最佳时机III（完成两笔交易）：二维数组，5种状态
4. 题目四：188. 买卖股票的最佳时机 IV（完成k笔交易）：二维数组，2*k+1种状态
5. 题目五：309. 最佳买卖股票时机含冷冻期（多笔交易，有冷冻期）：二维数组，4种状态
6. 题目六：714. 买卖股票的最佳时机含手续费（多笔交易，增加手续费）：二维数组，两种状态