1.题目解析

题目来源：123.买卖股票的最佳时机|||——力扣

测试用例

2.算法原理

1.状态表示

根据题目可以看出每一天的状态都有"买入""卖出"两种状态，但是还有交易次数限制，因此创建两个二维dp表，f表存储"买入"状态的利润，g表存储"卖出"状态的利润

f[i][j]：第i天结束时处于"买入"状态的最大利润，此时总交易次数为j次

g[i][j]：第i天结束时处于"卖出"状态的最大利润，此时总交易次数为j次

2.状态转移方程

3.初始化

根据状态转移方程可知填表时每个位置都需要前一个位置的数据，因此需要初始化两个表第一行的元素，如下图

其中的负无穷是-0x3f3f3f3f，指的是INT_MIN的一半，是为了避免栈溢出

4.填表顺序

从上到下，每一行从左到右，两个表一起填入

5.返回值 

返回处于"卖出"状态的最后一天内最高的利润，因为处于"买入"状态说明手上依旧持有股票，一定不是最大利润则不考虑f表

3.实战代码

class Solution {
public:const int INF = 1e5 + 1;int maxProfit(vector<int>& prices) {int n = prices.size();vector<vector<int>> f(n, vector<int>(3, -INF));vector<vector<int>> g(n, vector<int>(3, -INF));f[0][0] = -prices[0];g[0][0] = 0;for (int i = 1; i < n; i++) {for (int j = 0; j < 3; j++) {f[i][j] = max(f[i - 1][j], g[i - 1][j] - prices[i]);g[i][j] = g[i - 1][j];if (j >= 1) {g[i][j] = max(g[i][j], f[i - 1][j - 1] + prices[i]);}}}int ret = 0;for (int j = 0; j < 3; j++) {ret = max(ret, g[n - 1][j]);}return ret;}
};