【Leetcode动态规划--股票问题】121,122,123.买卖股票的最佳时机 I I III 188.买卖股票的最佳时机IV 309.最佳买卖股票时机含冷冻期 714.买卖股票的最佳时机含手续费_股票交易有k次交易机会代码

整个股票问题目录

整个股票问题的递推的一个重要理解笔记

1.重要递推理解

2.总结递推记忆

a.递推就是状态k由状态k-1，k推出

b.并且由k-1状态推出时，当前k代表买入就 -prices[i]，当前k代表卖出就 +prices[i]

c.n次交易就代表有2n种状态加上没有操作这一种状态就是 2n+1种状态，也是dp的维度

d.理论上dp使用三维数组就是最真是最好理解题意的，dp[i][j][k] , 第i天也就是第i支股票，第j次买卖，k表示买还是卖的状态，但是具体题目我们可以适当降维以减少代码复杂度！

Leetcode121(买卖一次)

1.问题描述

2.解决方案

解法一：二维数组dp

代码sxl上有详细过程，这里只做强调
1.dp的定义比较正常
2.递推比较有意思，在上面的笔记已经提到了，一开始自己设计的递推是有问题的后来改进对了
3.初始化看定义

//二维数组
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        //1.
        int len=prices.size();
        if(len==0) return 0;

        //2.dp[i][0]持有  dp[i][1]不持有
        vector<vector<int> > dp(len,vector<int>(2));
        dp[0][0]=-prices[0];
        dp[0][1]=0;

        //3.
        for(int i=1;i<len;i++){
            dp[i][0]=max(dp[i-1][0],-prices[i]);
            dp[i][1]=max(dp[i-1][1],dp[i-1][0]+prices[i]);
        }

        //4.
        return dp[len-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

解法二：一维滚动数组dp

代码sxl上有详细过程，这里只做强调
其他和解法一，一摸一样，只是这个使用了滚动数组，也就是总共只记录两个股票的二元组状态

//二维滚动数组
class Solution1 {
public:
    int maxProfit(vector<int>& prices) {
        //1.
        int len=prices.size();
        if(len==0) return 0;

        //2.dp[i][0]持有  dp[i][1]不持有
        vector<vector<int> > dp(2,vector<int>(2));
        dp[0][0]=-prices[0];
        dp[0][1]=0;

        //3.
        for(int i=1;i<len;i++){
            int indexCur=i%2;
            //int indexPre=(i%2+1)%2;
            int indexPre=(i-1)%2;
            dp[indexCur][0]=max(dp[indexPre][0],-prices[i]);
            dp[indexCur][1]=max(dp[indexPre][1],dp[indexPre][0]+prices[i]);
        }

        //4.
        return dp[(len-1)%2][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

Leetcode122(买卖多次)

1.问题描述

2.解决方案

相比121题目就改了一处，至于为什么改完就由一次交易变成了多次交易可以看上面的手写笔记！
121：一次交易求最大值

dp[indexCur][0]=max(dp[indexPre][0],-prices[i]);
dp[indexCur][1]=max(dp[indexPre][1],dp[indexPre][0]+prices[i]);
1
2

122：多次交易求最大值

dp[indexCur][0]=max(dp[indexPre][0],dp[indexPre][1]-prices[i]);
dp[indexCur][1]=max(dp[indexPre][1],dp[indexPre][0]+prices[i]);
1
2

//二维滚动数组
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        //1.
        int len=prices.size();
        if(len==0) return 0;

        //2.dp[i][0]持有  dp[i][1]不持有
        vector<vector<int> > dp(2,vector<int>(2));
        dp[0][0]=-prices[0];
        dp[0][1]=0;

        //3.
        for(int i=1;i<len;i++){
            int indexCur=i%2;
            //int indexPre=(i%2+1)%2;
            int indexPre=(i-1)%2;
            dp[indexCur][0]=max(dp[indexPre][0],dp[indexPre][1]-prices[i]);
            dp[indexCur][1]=max(dp[indexPre][1],dp[indexPre][0]+prices[i]);
        }

        //4.
        return dp[(len-1)%2][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

Leetcode123(买卖两次)

1.问题描述

2.解决方案

代码sxl上有详细过程，这里只做强调
1.递推不用多说了。非常巧妙，上面有总结
2.初始化只有1，3状态需要赋值，其他零
3.状态1由状态0,1推出； 状态2由状态1,2推出； 状态3由状态2,3推出； 状态4由状态3,4推出，并且买入就减，卖出就加
4.我们发现dp[2]用的是今天的dp[1]，我们发现dp[3]用的是今天的dp[2]，我们发现dp[4]用的是今天的dp[3]，那为什么正确呢，因为具体分析后发现正好是正确的两种状态，如下图

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        //1.
        int len=prices.size();

        //2.
        vector<int> dp(5,0);
        dp[1]=-prices[0];
        dp[3]=-prices[0];

        //3.
        for(int i=1;i<len;i++){
            int item=prices[i];
            dp[0]=dp[0];
            dp[1]=max(dp[1],dp[0]-item);
            dp[2]=max(dp[2],dp[1]+item);
            dp[3]=max(dp[3],dp[2]-item);
            dp[4]=max(dp[4],dp[3]+item);
        }

        //4.
        return dp[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

Leetcode188(买卖k次)

1.问题描述

2.解决方案

代码sxl上由详细解释，这只做强调
1.其他都老生长谈了，递推就是状态k由状态k-1，k推出
2.并且由k-1状态推出时，当前k代表买入就 -prices[i]，当前k代表卖出就 +prices[i]

class Solution {
public:
    int maxProfit(int k, vector<int>& prices) {
        //1.
        int len=prices.size();
        int lenDp=1+k*2;
        if(len==0||k==0) return 0;

        //2.dp[1,3,,]买入 dp[2,4,,]卖出
        vector<int> dp(lenDp,0);
        for(int i=1;i<lenDp;i+=2){
            dp[i]=-prices[0];
        }

        //3.
        for(int i=1;i<len;i++){
            for(int j=1;j<lenDp;j++){
                if(j%2!=0) dp[j]=max(dp[j],dp[j-1]-prices[i]);
                if(j%2==0) dp[j]=max(dp[j],dp[j-1]+prices[i]);
            }
        }

        //4.
        return dp[lenDp-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

Leetcode309(买卖多次，卖出第一天冷冻)

1.问题描述

2.解决方案

a.四个状态的归纳很重要

b.递推得好好想，自己推导一遍就好

c.初始化和上面一样买入状态初始化为-prices[0] ，其他的统一初始化为0

d.下面的代码是使用二维滚动数组实现的，也可以用二位普通数组实现

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        //1.
        int len=prices.size();
        if(len==0) return 0;

        //2.
        vector<vector<int> > dp(2,vector<int>(4,0));
        dp[0][0]=-prices[0];

        //3.
        for(int i=1;i<len;i++){
            int indexCur=i%2;
            int indexPre=(i-1)%2;
            dp[indexCur][0]=max(dp[indexPre][0],max(dp[indexPre][1],dp[indexPre][3])-prices[i]);
            dp[indexCur][1]=max(dp[indexPre][1],dp[indexPre][3]);
            dp[indexCur][2]=dp[indexPre][0]+prices[i];
            dp[indexCur][3]=dp[indexPre][2];
        }

        //4.
        int indexEnd=(len-1)%2;
        return max(dp[indexEnd][1],max(dp[indexEnd][2],dp[indexEnd][3]));
    }
};
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

Leetcode714(买卖多次，每次交易有手续费)

1.问题描述

2.解决方案

a.由于题目是多次交易且含手续费，所以和122几乎没什么区别，只要在买入或者卖出是增加一个手续费即可
122：多次交易

dp[indexCur][0]=max(dp[indexPre][0],dp[indexPre][1]-prices[i]);
dp[indexCur][1]=max(dp[indexPre][1],dp[indexPre][0]+prices[i]);
1
2

714：多次交易只是卖出时减去一个fee即可

dp[indexCur][0]=max(dp[indexPre][0],dp[indexPre][1]-prices[i]);
dp[indexCur][1]=max(dp[indexPre][1],dp[indexPre][0]+prices[i]-fee);
1
2

class Solution {
public:
    int maxProfit(vector<int>& prices, int fee) {
        //1.
        int len=prices.size();
        if(len==0) return 0;

        //2.dp[i][0]持有  dp[i][1]不持有
        vector<vector<int> > dp(2,vector<int>(2));
        dp[0][0]=-prices[0];
        dp[0][1]=0;

        //3.
        for(int i=1;i<len;i++){
            int indexCur=i%2;
            //int indexPre=(i%2+1)%2;
            int indexPre=(i-1)%2;
            dp[indexCur][0]=max(dp[indexPre][0],dp[indexPre][1]-prices[i]);
            dp[indexCur][1]=max(dp[indexPre][1],dp[indexPre][0]+prices[i]-fee);
        }

        //4.
        return dp[(len-1)%2][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