【动态规划】买卖股票的最佳时机Ⅲ

题目链接https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-iii/description/classSolution{public:constintINF0x3f3f3f3f;intmaxProfit(vectorintprices){/*时空复杂度O(n)*/intnprices.size();// 1. 创建dp表vectorvectorintf(n,vectorint(3,-INF));autogf;// 2. 初始化f[0][0]-prices[0],g[0][0]0;// 3. 填表for(inti1;in;i)for(intj0;j3;j){f[i][j]max(f[i-1][j],g[i-1][j]-prices[i]);g[i][j]g[i-1][j];if(j1)g[i][j]max(g[i-1][j],f[i-1][j-1]prices[i]);}// 4. 返回值// return max(g[n - 1][0], max(g[n - 1][1], g[n - 1][2]));intret0;for(intj0;j3;j)retmax(ret,g[n-1][j]);returnret;}};