stone

动态规划整理(长期更新)
股票系列1. Best Time to Buy and Sell Stock只能购买一次,则选取前i个中最小的和当...
扫描右侧二维码阅读全文
01
2019/03

动态规划整理(长期更新)

股票系列

1. Best Time to Buy and Sell Stock

只能购买一次,则选取前i个中最小的和当前作差,记录最大的

2. Best Time to Buy and Sell Stock II

可以购买任意次,则直接dp,注意初始状态

vector<vector<int>> dp(2,vector<int>(prices.size()+1,0));
dp[0][0] = INT_MIN;
for (int i = 1;i<=prices.size();++i){
  dp[0][i] = max(dp[0][i-1],dp[1][i-1]-prices[i-1]);
  dp[1][i] = max(dp[1][i-1],dp[0][i-1]+prices[i-1]);
}
return max(dp[0][prices.size()],dp[1][prices.size()]);

3. Best Time to Buy and Sell Stock III

只能交易两次,使用状态机,写状态的转移

vector<vector<int>> dp(K,vector<int>(n,0));

for (int k = 1;k<K;k++){
    int tmp = dp[k-1][0]-prices[0];
    for (int i = 1;i<n;i++){
        dp[k][i] = max(dp[k][i-1],prices[i]+tmp);
        tmp = max(tmp,dp[k-1][i]-prices[i]);
        profile = max(profile,dp[k][i]);
    }
}

4. Best Time to Buy and Sell Stock IV

可以购买k次

if (K-1>n/2){ // simple case
    int ans = 0;
    for (int i=1; i<n; ++i){
        ans += max(prices[i] - prices[i-1],0);
    }
    return ans;
}

vector<int> buy(K, INT_MIN), sale(K, 0);
for(int i=0; i<n; i++){
    for(int j=1; j<K; j++){
        buy[j] = max(buy[j], sale[j-1]-prices[i]);
        sale[j] = max(sale[j], buy[j] + prices[i]);
    }
}
return sale[K-1];

5. Best Time to Buy and Sell Stock with Cooldown

在出售之后必须要冷却一天

int n = prices.size();
vector<vector<int>> dp(3,vector<int>(prices.size()+1));
dp[0][0] = -prices[0];
    
for (int i =1;i<=prices.size();i++){
    dp[0][i] = max(dp[2][i-1]-prices[i-1],dp[0][i-1]);
    dp[1][i] = max(dp[0][i-1]+prices[i-1],dp[1][i-1]);
    dp[2][i] = max(dp[1][i-1],dp[2][i-1]);
    // cout<<i<<":"<<dp[0][i]<<","<<dp[1][i]<<","<<dp[2][i]<<endl;
}
    
return max(max(dp[0][n],dp[1][n]),dp[2][n]);

6. [Best Time to Buy and Sell Stock with Transaction Fee](https://leetcode.com/problems/best-time-to-buy-and-sell-stock-with-transaction-fee/

每个完整的交易都要交手续费

int n = prices.size();
if (n<2) return 0;

int b = -prices[0];
int s = 0;

int t = b;
for (int i = 1;i<=n;i++){
    t = b;
    b = max(s-prices[i-1],b);
    s = max(t+prices[i-1]-fee,s);
}

return max(b,s);
Last modification:March 1st, 2019 at 11:28 am
If you think my article is useful to you, please feel free to appreciate

Leave a Comment