题解 | #买卖股票的最好时机(三)#dp+滚动数组

没本事理解四个变量版本的代码，所以用了完整的dp，但是用了滚动数组优化内存

理论上会有内存消耗/2，但空间复杂度同样O(k)的版本，不过因为代码比较繁琐懒得写了……

#include <climits>
#include <vector>
#include <iostream>
#include <ostream>
using namespace std;

int main() {
    int n, t,i,j,k,cur,prev;
    static int max_deal=2;
    cin >> n;
    vector<vector<vector<int>>> dp(2,vector<vector<int>>(max_deal+1,vector<int>(2,0)));
    //dp[i][j][k]代表第i天，最多已买入次数（含今次），今天结束时是否持股,存储此时的账户最大余额
    cin>>t;
    for(i=0;i<2;++i){
        for(j=1;j<=max_deal;++j){
            dp[i][j][1]=-t;
        }
    }

    for(i=1;i<n;++i){
        cin>>t;
        cur=i%2;
        prev=(i-1)%2;
        for(j=1;j<=min(max_deal,(i+1)/2);++j){
            dp[cur][j][0]=max(dp[prev][j][0],dp[prev][j][1]+t);//保持空仓，或卖出手中
            dp[cur][j][1]=max(dp[prev][j][1],dp[prev][j-1][0]-t);//买入，或保持持仓。如果总交易只有1则不考虑上次交易
            //cout<<i<<' '<<j<<' '<<dp[i][j][0]<<' '<<dp[i][j][1]<<"|";
        }  
      // cout<<endl;
    }
    cout<<dp[cur][max_deal][0]<<endl;
    }