动态规划—股票问题AK_股市ak结构

1.整体框架

1.1定义dp数组

// i 表示第i天 
// k 表示可以操作的次数 
// 0 表示不持有股票， 1 表示持有股票
// 一定要记仔细定义，不过我相信你会经常来这里看的
dp[i][k][0]	= max(dp[i-1][k][0], dp[i-1][k][1] + prices[i])														
              max(选择	rest     选择    sell		      )

解释：今天 未持有 股票，有两种可能：

 1.我昨天 未持有 ，今天选择 rest，所以我今天 未持有；
 2.我昨天 持有 ，但是今天我 sell，所以我今天 未持有。
dp[i][k][1]	= max(dp[i-1][k][1], dp[i-1][k-1][0] - prices[i])														
			  max(选择  rest      选择	 buy              )
解释：今天 持有 股票，有两种可能： 
 1.我昨天就 持有 着股票，然后今天选择 rest，所以我今天 持有；
 2.我昨天 未持有，但今天我选择 buy，所以今天我 持有
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

1.2 basecase(起始状态)

dp[-1][k][0] = 0 
解释：因为i是从0开始的，所以i=-1意味着还没有始，这时候的利润当然是0。 
dp[-1][k][1] = -infinity 
解释：还没开始的时候，是不可能持有股票的，⽤负⽆穷表⽰这种不可能。
dp[i][0][0]	= 0 
解释：因为k是从1开始的，所以k = 0意味着根本不允许交易，这时候利润当然是	0	。 
dp[i][0][1]	= -infinity 
解释：不允许交易的情况下，是不可能持有股票的，⽤负⽆穷表⽰这种不可能。
1
2
3
4
5
6
7
8

2.买卖股票的最佳时机(leetcode121)

// 为了减小空间复杂度
// 我知道你看不懂哒，再回到上面去瞅瞅dp的定义
// 1.显然操作只有一次故 k = 1为常数
// 2.没有特殊条件哒~
// 你可能对我这个dp_i_1有很多问号,你就想成他取负号就好
// 例如这里两个状态转移你可以改写为：
//  dp_i_0 = max(dp_i_0, -dp_i_1 + prices[i]);
//  dp_i_1 = min(dp_i_1, prices[i]);//这儿是min 喔

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int dp_i_0 = 0, dp_i_1 = INT_MIN;
        for (int i = 0; i < prices.size(); i++) {
            
            dp_i_0 = max(dp_i_0, dp_i_1 + prices[i]);
            dp_i_1 = max(dp_i_1, -prices[i]);
        }
        return dp_i_0;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

3.买卖股票的最佳时机II(leetcode122）

// 看不懂就回去瞅瞅dp的定义
// 1.无数次， 顾直接压缩掉 k，
// 2.正因是无数次，我们需要temp记录上一次买入股票的价格
// 3.对于持有股票的状态，显然应当修改为：
// dp_i_1 = max(dp_i_1, temp - prices[i]);

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int dp_i_0 = 0, dp_i_1 = INT_MIN;
        for (int i = 0; i < prices.size(); i++) {
            int temp = dp_i_0;
            dp_i_0 = max(dp_i_0, dp_i_1 + prices[i]);
            dp_i_1 = max(dp_i_1, temp - prices[i]);
        }
        return dp_i_0;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

4.买卖股票的最佳时机III(leetcode123）

// 不能理解就回去看看dp的定义！！！
// 1. k = 2 这个时候就不能直接状态压缩掉k
// 2.但同样为了降低空间复杂度，我们就定义两组不就好了吗？
// 3.对第一次选择状态转移方程直接可以和k = 1的一样呀
// 4.k = 2的时候， 你想想无穷次的时候的定义,不过是吧temp转变为了dp_i_1_0
// 没想明白就回去看dp定义，用dp数组自己推理状态压缩
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int len = prices.size();
        int dp_i1_0 = 0, dp_i1_1 = INT_MIN;
        int dp_i2_0 = 0, dp_i2_1 = INT_MIN;
        for(auto price : prices) {
            dp_i2_0 =  max(dp_i2_0, dp_i2_1+price);
            dp_i2_1 = max(dp_i2_1, dp_i1_0 - price);
            dp_i1_0 =  max(dp_i1_0, dp_i1_1+price);
            dp_i1_1 = max(dp_i1_1, -price);
        }
        return dp_i2_0;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

5.买卖股票的最佳时机IV(LeetCode188)

// 不懂就回去看dp定义！！！
// k是任意次数
// 显然状压是状压不了了
// 1.k >= n/2 这种情况等价于无穷次，想一一下为什么
// 2.直接使用dp定义写代码
// 3.basecase的定义：
// 对 k = anynum > 0 的dp_0 赋值 0
// 对 k = anynum > 0 的dp_1 赋值 -prices[0]
// 4.不是吧，我都强调了这么多遍了你还记不住正规的状态转移？
class Solution {
public:
    int maxProfit(int k, vector<int>& prices) {
        int n = prices.size();
        if (k >= n/2) {
            int dp_i_0 = 0, dp_i_1 = INT_MIN;
            for (auto price : prices) {
                int t = dp_i_0;
                dp_i_0 = max (dp_i_0, dp_i_1 + price);
                dp_i_1 = max(dp_i_1, t - price);
            }
            return dp_i_0;
        }
        
        int dp[n][k+1][2];
		// 这里先赋值 0;
		// 然后对 k = 0 的 dp_1赋值 INT_MIN
        memset(dp, 0, sizeof(dp));
        for(int i=0; i<n; i++)
            dp[i][0][1] = INT_MIN;
        
        for (int i = 0; i < n; i++) {
            for (int j = 1; j <= k; j++) {
                if(i == 0) {
                    dp[0][j][0] = 0;
                    dp[0][j][1] = -prices[0]; 
                } else {
                    dp[i][j][0] = max(dp[i-1][j][0], dp[i-1][j][1] + prices[i]);
                    dp[i][j][1] = max(dp[i-1][j][1], dp[i-1][j-1][0] - prices[i]);
                }
            }
        }
        return dp[n-1][k][0];
    }
};
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
40
41
42
43
44

6.最佳买卖股票时机含冷冻期(Leetcode309)

// 看不懂就回去看dp定义
// 1.考虑无穷天的代码
// 2.由于含冷冻期 执行buy的时候只能是休息一天后买来的
// 3.非常简单 我们再定义一个dp_pre_0来记录两天前的状态
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int dp_i_0 = 0, dp_i_1 = INT_MIN;
        int dp_pre_0 = 0;
        for (int i = 0; i < prices.size(); i++) {
            int temp = dp_i_0;
            dp_i_0 = max(dp_i_0, dp_i_1 + prices[i]);
            dp_i_1 = max(dp_i_1, dp_pre_0 - prices[i]);
            dp_pre_0 = temp;
        }
        return dp_i_0;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

7. 买卖股票的最佳时机含手续费(Leetcode714)

// 看不懂就回去看dp定义
// 相信到这里你已经很熟悉了
// 1.关注无限次的代码
// 2.这有啥？不就是在买股票的时候加了一个手续费吗
// 3.修改方程：
// dp_i_1 = Math.max(dp_i_1, temp - prices[i] -fee);
// 你同样可以写成：
// dp_i_0 = Math.max(dp_i_0, -dp_i_1 + prices[i]);
// dp_i_1 = Math.min(dp_i_1, prices[i] + fee - temp);
class Solution {
    public int maxProfit(int[] prices, int fee) {
        int n = prices.length;
        int dp_i_0 = 0, dp_i_1 = Integer.MIN_VALUE;
        int dp_pre_0 = 0;
        for (int i = 0; i < n; i++) {
            int temp = dp_i_0;
            dp_i_0 = Math.max(dp_i_0, dp_i_1 + prices[i]);
            dp_i_1 = Math.max(dp_i_1, temp - prices[i] -fee);
        }
        return dp_i_0;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

写在最后

呀呀~股票问题是不是很简单呢？
要是对你有帮助的话，赶紧夸夸世界第一可爱的我吧~嘻嘻