leetcode股票问题

动态规划的思想，遍历所有可能的情况

题目条件：天数n，交易次数k，持有股票情况0/1

maxProfit(vector<int> &prices, int k)
{
    int n = prices.size();
    //n天，交易k次，持有/不持有股票
    int dp[n][k+1][2] = {0};
    for(int i=0;i<=n;++i)
    {
        for(int j=k;j>=1;j--)
        {
            //单独处理的case
            if(i-1==0)
            {
                //第一天不持有股票，所以利润为0
                dp[i][j][0] = 0;
                //第一天购买了股票，利润为负数，扣除成本
                dp[i][j][-1] = -prices[0];
                continue;
            }
            //第i天持有股票和不持有股票最大利润
            //重点，dp[i-1][j][1]+prices[i]这里，只能在买入的时候进行标记
            dp[i][j][0] = max(dp[i-1][j][0], dp[i-1][j][1]+prices[i]);  //不持有分两种情况，昨天不持有和第i天卖掉
            dp[i][j][1] = max(dp[i-1][j-1][0]-prices[i], dp[i-1][j][1]); //持有分两种情况，昨天持有和昨天买入
        }
    }
    //最大利润为最后一天，手中不持有股票
    return dp[n-1][k][0];
}