188. Best Time to Buy and Sell Stock IV

参考:团灭股票问题

问题:

股票问题:

给出一组一支股票每日的价格数组。prices[]

每一天的操作可以为:买buy,卖sell,不操作rest

一次交易从buy开始,若限制在K次交易以内,求可获得的最大收益是多少。

解法:DP(动态规划)

1.确定【状态】:

  • 当前的天数:第 i 天
  • 当前经过的交易次数:第 k 次
  • 当前的股票持有状况:p:0未持有(待买入),1 持有(待卖出)

2.确定【选择】:

  • 当前p=0(未持有,待买入状态):
    • 选择 1 :由本日卖出sell导致:dp[i-1][k][1]+prices[i] (昨天持股+今天卖出prices[i])
    • 选择 2:本日不操作rest:  dp[i-1][k][0]             (昨天未持股+今天不操作)
  • 当前p=1(持有,待卖出状态):
    • 选择 1 :由本日买入buy导致:dp[i-1][k][0]-prices[i] (昨天未持股+今天买入prices[i])
    • 选择 2:本日不操作rest:  dp[i-1][k][1]              (昨天持股+今天不操作)

3. dp[i][k][p]的含义:

今天为第i天,交易k次,持有状态为p的状态下,持有的最大收益。

4. 状态转移:

dp[i][k][p]= 

  • 当前p=0(未持有,待买入状态):MAX {
    • 选择 1 :由本日卖出sell导致:dp[i-1][k][1]+prices[i] (昨天持股+今天卖出prices[i])
    • 选择 2:本日不操作rest:  dp[i-1][k][0]             (昨天未持股+今天不操作) }
  • 当前p=1(持有,待卖出状态):MAX {
    • 选择 1 :由本日买入buy导致:dp[i-1][k][0]-prices[i] (昨天未持股+今天买入prices[i])
    • 选择 2:本日不操作rest:  dp[i-1][k][1]              (昨天持股+今天不操作)}

5. base case:

  • i==0
    • dp[0][k][0]= 0
    • dp[0][k][1]= -∞(不可能存在的情况,用-∞表示)
  • k==0
    • dp[i][0][0]= 0
    • dp[i][0][1]= -∞(不可能存在的情况,用-∞表示)

⚠️ 注意:

本问题中,若交易次数k大于每天都交易的最大交易次数prices.size/2,那么,可类似将k看作无限制交易次数。

那么本问题的状态转移公式即可简化:(直接调用函数:maxProfit_k_inf)

3状态->2状态:天数+股票持有状态

dp[i][p]= 

  • 当前p=0(未持有,待买入状态):MAX {
    • 选择 1 :由本日卖出sell导致:dp[i-1][1]+prices[i] (昨天持股+今天卖出prices[i])
    • 选择 2:本日不操作rest:  dp[i-1][0]             (昨天未持股+今天不操作) }
  • 当前p=1(持有,待卖出状态):MAX {
    • 选择 1 :由本日买入buy导致:dp[i-1][0]-prices[i] (昨天未持股+今天买入prices[i])
    • 选择 2:本日不操作rest:  dp[i-1][1]              (昨天持股+今天不操作)}

 

代码参考:

 1 class Solution {
 2 public:
 3     //dp[i][k][p]: the most profit for i days, k times transaction, now have p position. 
 4     //i: day i
 5     //k: k-th transaction
 6     //p: position:0(pre-act is sell) or 1(pre-act is buy)
 7     //case_1: p=0 (act is sell):dp[i][k][0]= max:
 8     //       opt_1: act = sell: dp[i-1][k][1]+prices[i]
 9     //       opt_2: act = rest: dp[i-1][k][0]
10     //case_2: p=1 (act is buy):dp[i][k][1]= max:
11     //       opt_1: act = buy : dp[i-1][k-1][0]-prices[i]
12     //       opt_2: act = rest: dp[i-1][k][1]
13     //base case:
14     //dp[0][k][0] = 0
15     //dp[0][k][1] = -infinity(imposible)
16     //dp[i][0][0] = 0
17     //dp[i][0][1] = -infinity(imposible)
18     //buy=>start one transaction.
19     int maxProfit(int K, vector<int>& prices) {
20         int n=prices.size();
21         if(K>n/2) return maxProfit_k_inf(prices);
22         vector<vector<vector<int>>> dp(n+1, vector<vector<int>>(K+1, vector<int>(2,0)));
23         for(int i=0; i<=n; i++) {
24             dp[i][0][0] = 0;
25             dp[i][0][1] = INT_MIN;
26         }
27         for(int k=0; k<=K; k++) {
28             dp[0][k][0] = 0;
29             dp[0][k][1] = INT_MIN;
30         }
31         for(int i=1; i<=n; i++) {
32             for(int k=1; k<=K; k++) {
33                 dp[i][k][0] = max(dp[i-1][k][1]+prices[i-1], dp[i-1][k][0]);
34                 dp[i][k][1] = max(dp[i-1][k-1][0]-prices[i-1], dp[i-1][k][1]);
35             }
36         }
37         return dp[n][K][0];
38     }
39     // k->+infinity -> k==k-1
40     // dp[i][k][0] = max(dp[i-1][k][1]+prices[i-1], dp[i-1][k][0]);
41     // dp[i][k][1] = max(dp[i-1][k][0]-prices[i-1], dp[i-1][k-1][1]);
42     //->
43     // dp[i][0] = max(dp[i-1][1]+prices[i-1], dp[i-1][0]);
44     // dp[i][1] = max(dp[i-1][0]-prices[i-1], dp[i-1][1]);
45     //->
46     // dp_0 = max(dp_1+prices[i-1], dp_0);
47     // dp_1 = max(dp_0-prices[i-1], dp_1);
48     int maxProfit_k_inf(vector<int>& prices) {
49         int n=prices.size();
50         int dp_0 = 0, dp_1 = INT_MIN;
51         for(int i=1; i<=n; i++) {
52             int temp = dp_0;
53             dp_0 = max(dp_1+prices[i-1], dp_0);
54             dp_1 = max(temp-prices[i-1], dp_1);
55         }
56         return dp_0;
57     }
58 };

♻️ 优化:

空间复杂度:3维->2维

去掉 i 

压缩所有行到一行。

使用:左上角+左下角。

因此倒序遍历k

 

代码参考:

 1 class Solution {
 2 public:
 3     int maxProfit(int K, vector<int>& prices) {
 4         int n=prices.size();
 5         if(K>n/2) return maxProfit_k_inf(prices);
 6         vector<vector<int>> dp(K+1, vector<int>(2,0));
 7 
 8         for(int k=0; k<=K; k++) {
 9             dp[k][0] = 0;
10             dp[k][1] = INT_MIN;
11         }
12         for(int i=1; i<=n; i++) {
13             for(int k=K; k>=1; k--) {
14                 dp[k][0] = max(dp[k][1]+prices[i-1], dp[k][0]);
15                 dp[k][1] = max(dp[k-1][0]-prices[i-1], dp[k][1]);
16             }
17         }
18         return dp[K][0];
19     }
20 
21     int maxProfit_k_inf(vector<int>& prices) {
22         int n=prices.size();
23         int dp_0 = 0, dp_1 = INT_MIN;
24         for(int i=1; i<=n; i++) {
25             int temp = dp_0;
26             dp_0 = max(dp_1+prices[i-1], dp_0);
27             dp_1 = max(temp-prices[i-1], dp_1);
28         }
29         return dp_0;
30     }
31 };

 

上一篇:ofb


下一篇:[LeetCode] 188. Best Time to Buy and Sell Stock IV