题目描述
给你一个整数数组 prices 和一个整数 k ，其中 prices[i] 是某支给定的股票在第 i 天的价格。 设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。也就是说，你最多可以买 k 次，卖 k 次。
注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
示例 ：
输入：k = 2, prices = [2,4,1] 输出：2 解释：在第 1 天 (股票价格 = 2) 的时候买入，在第 2 天 (股票价格 = 4) 的时候卖出，这笔交易所能获得利润 = 4-2 = 2 。
解题思路
数组定义
在这个解决方案中，我们使用了两个二维数组f和g来跟踪每一天和每一次交易后的最大利润。
f[i][j]：表示第i天结束后，进行了j次交易（注意这里的j次交易包括买入和卖出），并且当前手中持有股票时的最大利润。g[i][j]：表示第i天结束后，进行了j次交易，并且当前手中没有股票时的最大利润。
初始化
f[0][0]：第一天没有交易，如果持有股票，则必须是在第一天买入的，所以利润是-prices[0]。g[0][0]：第一天没有交易，没有股票，利润为0。- 对于
j > 0的情况，第一天不可能完成多于一次的交易，所以f[0][j]和g[0][j]都初始化为一个非常小的数（例如INT_MIN或-0x3f3f3f），表示这些状态是无效的。
状态转移
对于每一天i和每一次交易数j：
- 更新
f[i][j]：你可以选择在第i天继续持有股票（即继承前一天的f[i-1][j]），或者你可以选择在第i天买入股票（但前提是之前已经完成了j-1次交易，即从前一天的g[i-1][j-1]状态转移而来，并减去今天的股票价格）。 - 更新
g[i][j]：你可以选择在第i天不进行操作（即继承前一天的g[i-1][j]），或者你可以选择在第i天卖出股票（但前提是之前已经买入了股票，即从前一天的f[i-1][j]状态转移而来，并加上今天的股票价格）。
状态转移方程
1. f[i][j] 的状态转移方程
f[i][j] 表示第 i 天结束后，完成了 j 次交易（包括买入和卖出），并且当前手中持有股票时的最大利润。
- 如果我们在第
i天选择不进行操作（即继续持有前一天买入的股票），那么f[i][j]的值应该等于前一天的相同状态f[i-1][j]。 - 如果我们在第
i天选择买入股票（这必须是在之前已经完成了j次交易之后），那么我们需要从前一天的“不持有股票但已完成j次交易”的状态g[i-1][j]转移而来，并减去今天的股票价格prices[i]。
因此，f[i][j] 的状态转移方程为：
f[ i ][ j ] = max(f[ i − 1 ][ j ],g[ i − 1 ][ j ] − prices[ i ])
2. g[i][j] 的状态转移方程
g[i][j] 表示第 i 天结束后，完成了 j 次交易，并且当前手中没有股票时的最大利润。
- 如果我们在第
i天选择不进行操作（即保持前一天的状态），那么g[i][j]的值应该等于前一天的相同状态g[i-1][j]。 - 如果我们在第
i天选择卖出股票（卖出股票后j++,在第 i - 1 天时实际完成了 j - 1 次交易），那么我们需要从前一天的“持有股票且已完成j-1次交易”的状态f[i-1][j-1]转移而来，并加上今天的股票价格prices[i]。
因此，g[i][j] 的状态转移方程为：
g[i][j]=max(g[i−1][j],f[i−1][j−1]+prices[i])
注意：这里对于 j = 0 的情况，我们需要对其进行处理。
结果
最后，我们遍历g[n-1][j]（其中n是价格数组的长度），找到其中的最大值，这就是我们可以获得的最大利润。
class Solution {
public:int maxProfit(int k, vector<int>& prices) {int n = prices.size();// 两个二维数组// f[i][j] : 第i天结束后 完成了j次交易，此时处于买入状态下的最大利润// g[i][j] : 第i天结束后 完成了j次交易，此时处于卖出状态下的最大利润vector<vector<int>> f(n, vector<int>(k + 1, 0));vector<vector<int>> g(n, vector<int>(k + 1, 0));// 初始化f[0][0] = 0 - prices[0];g[0][0] = 0;for (int j = 1; j < k + 1; j++) {f[0][j] = 0 - 0x3f3f3f;g[0][j] = 0 - 0x3f3f3f;}// 填表for (int i = 1; i < n; i++) {for (int j = 0; j <= k; j++) {f[i][j] = max(f[i - 1][j], g[i - 1][j] - prices[i]);// g[i][j] = max(g[i - 1][j], f[i - 1][j - 1] +// prices[i]);//f[i-1][j-1] 因为完成卖出操作后 操作数j++了g[i][j] = g[i - 1][j];if (j > 0)g[i][j] = max(g[i][j], f[i - 1][j - 1] + prices[i]);}}int ret = 0;for (int j = 0; j <= k; j++) {ret = max(ret, g[n - 1][j]);}return ret;}
};
