为第三方网站做推广,网络营销工具中,seo和sem的关系为负关系,江门网站优化公司力扣原题链接#xff0c;点击跳转。
给定一个整数数组prices#xff0c;prices[i]表示股票在第i天的价格。你最多完成2笔交易。你不能同时参与多笔交易#xff08;你必须在再次购买前出售掉之前的股票#xff09;。设计一个算法计算最大利润。
我们用动态规划的思想来解决…力扣原题链接点击跳转。
给定一个整数数组pricesprices[i]表示股票在第i天的价格。你最多完成2笔交易。你不能同时参与多笔交易你必须在再次购买前出售掉之前的股票。设计一个算法计算最大利润。
我们用动态规划的思想来解决这个问题。首先确定状态表示。我们用f和g分别表示「买入」和「卖出」状态处于「买入」状态时手里有股票处于「卖出」状态时手里没有股票。用i表示第i天结束时的状态。用j表示当前完成了j笔交易。也就是说用f[i][j]表示在第i天结束时处于「买入」状态下完成了j笔交易此时的最大利润用g[i][j]表示在第i天结束时处于「卖出」状态下完成了j笔交易此时的最大利润。
接下来推导状态转移方程。首先考虑f[i][j]如果第i-1天结束时处于「买入」状态那么需要在第i天「持有股票」就能在第i天结束时依然处于「买入」状态由于「持有股票」并不会改变完成的交易次数也不会改变利润所以此时f[i][j]f[i-1][j]如果第i-1天结束时处于「卖出」状态那么需要在第i天「买入股票」就能在第i天结束时处于「买入」状态由于「买入股票」并不会改变完成的交易次数但是会使利润减少第i天的股票价格所以此时f[i][j]g[i-1][j]-prices[i]。由于要求的是最大利润所以f[i][j]max(f[i-1][j],g[i-1][j]-prices[i])。
接着考虑g[i][j]如果第i-1天结束时处于「买入」状态那么需要在第i天「卖出股票」就能在第i天结束时处于「卖出」状态由于「卖出股票」后就完成了一次完整的交易所以在第i-1天结束时的交易次数会比第i天结束时的交易次数少1即第i-1天结束时的交易次数是j-1同时「卖出股票」会使利润增多第i天的股票价格所以此时g[i][j]f[i-1][j-1]prices[i]如果第i-1天结束时处于「卖出」状态那么需要在第i天「观望」就会在第i天结束时依然处于「卖出状态」而「观望」并不会改变交易次数和利润所以此时g[i][j]g[i-1][j]。由于要求的是最大利润所以g[i][j]max(f[i-1][j-1]prices[i],g[i-1][j])。
接下来考虑初始化的问题。再次观察状态转移方程f[i][j]max(f[i-1][j],g[i-1][j]-prices[i])g[i][j]max(f[i-1][j-1]prices[i],g[i-1][j])。由于f[i][j]和g[i][j]都会依赖于i-1所以初始化2个表的最上面一行。注意到j的取值范围是[0,2]故需要初始化的坐标有(0,0)、(0,1)和(0,2)。不过(0,1)和(0,2)说明在第0天结束时已经至少完成了1笔交易也就是说会在第0天「买入后立刻卖出股票」这种操作是没有意义的因为浪费了交易次数。所以为了让(0,1)和(0,2)的值不影响取max的结果应该把这两个位置初始化为-∞即-0x3f3f3f3f注意不是INT_MIN防止计算g[i-1][j]-prices[i]时溢出。所以现在只需要考虑f[0][0]和g[0][0]。其中f[0][0]表示在第0天结束时处于「买入」状态只需要在第0天「买入股票」即f[0][0]-prices[0]g[0][0]表示在第0天结束时处于「卖出」状态只需要在第0天「观望」即g[0][0]0。
还有另一个地方有可能越界。注意到g[i][j]max(f[i-1][j-1]prices[i],g[i-1][j])会依赖于j-1所以理论上还需要初始化g表的最左边一列。但是这么做的话会让f表和g表对应不上导致细节问题更难处理。所以我们采取另一种方法。j代表的是交易次数之所以j-1有可能越界是因为这样算出来的交易次数是-1。既然不存在交易次数是-1的情况我们只需要判断一下如果j-1≥0才计算g[i][j]max(f[i-1][j-1]prices[i],g[i-1][j])否则g[i][j]g[i-1][j]即可。这样就不存在越界的风险了。
填表时应从上往下填每一行每一行从左往右填且f表和g表同时填。最终应返回g表的最后一行的最大值这是因为要想获取最大利润就一定要在最后一天结束时处于「卖出」状态且不确定此时的交易次数。我们来分析一下dp表的规模。由于没有加上虚拟节点所以行数应与实际天数相同即prices的元素个数n由于j的所有可能取值是0、1和2所以有3列。综上f表和g表的大小均为n×3。
class Solution {
public:int maxProfit(vectorint prices) {const int INF 0x3f3f3f3f;int n prices.size();// 创建dp表vectorvectorint f(n, vectorint(3, -INF));auto g f;// 初始化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 0)g[i][j] max(g[i][j], f[i-1][j-1] prices[i]);}}// 求g表最后一行的最大值return *max_element(g[n-1].begin(), g[n-1].end());}
};
这道题还有个终极版本力扣原题链接点击跳转。
把限定的交易次数从2次改为k次其余条件不变求最大利润。
分析思路完全一样。状态表示和状态转移方程不变。初始化方式不变依然是最上面一行除了f[0][0]-prices[0]和g[0][0]0之外都初始化为-∞。填表顺序不变。最后依然是返回g表最后一行的最大值。只有表的规模从n×3变为了n×(k1)。
代码的话只需要把上道题的代码的3修改为k1即可。事实上上道题就是本题中k2时的特殊情况。除此之外还有一个点值得优化最多的交易次数一定不会超过总天数的一半比如总天数是10天那么最多交易5次总天数是9天那么最多交易4次。
class Solution {
public:int maxProfit(int k, vectorint prices) {const int INF 0x3f3f3f3f;int n prices.size();// 交易次数不会超过总天数的一半k min(k, n/2);// 创建dp表vectorvectorint f(n, vectorint(k1, -INF));auto g f;// 初始化f[0][0] -prices[0];g[0][0] 0;// 填表for (int i 1; i n; i){for (int j 0; j k1; 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 0)g[i][j] max(g[i][j], f[i-1][j-1] prices[i]);}}// 求g表最后一行的最大值return *max_element(g[n-1].begin(), g[n-1].end());}
};
