参考:团灭股票问题
问题:
股票问题:
给出一组一支股票每日的价格数组。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 };