123. 买卖股票的最佳时机 III

状态表示：

• (f(i,0,k))：表示当前为第(i)天，手里没有股票，交易次数不超过(k)次的最大利润；
• (f(i,1,k))：表示当前为第(i)天，手里有股票，交易次数不超过(k)次的最大利润。

状态转移：
第(i)天手里没有股票有两种情况：

1. 第(i-1)天手里没有股票；
2. 第(i-1)天手里有股票，在第(i)天卖出，此时交易次数加一。

第(i)天手里有股票同样有两种情况：

1. 第(i-1)天手里有股票
2. 第(i-1)天手里没有股票，在第(i)天购入股票，此时仅购入了股票，没有卖出，故交易次数不变。

[f(i,0,k)=max (f(i-1,0,k),f(i-1,1,k-1)+prices[i]) \ f(i,1,k)=max(f(i-1,0,k)-prices[i],f(i-1,1,k)); ]

边界：

[f[0][0][0 sim 2] = 0，f[0][1][0 sim 2] = prices[0] ]

class Solution {
public:
    static const int N=1e5+10;
    int f[N][2][3];
    int maxProfit(vector<int>& prices) {
        int n=prices.size();

        for(int i=0;i<n;i++)
            for(int k=0;k<=2;k++)
            {
                if(i == 0)
                {
                    f[i][0][k]=0;
                    f[i][1][k]=-prices[i];
                }
                else
                {
                    f[i][0][k]=f[i-1][0][k];
                    if(k) f[i][0][k]=max(f[i][0][k],f[i-1][1][k-1]+prices[i]);
                    f[i][1][k]=max(f[i-1][1][k],f[i-1][0][k]-prices[i]);
                }
            }
        return f[n-1][0][2];
    }
};