东莞网站建设全过程,外包网站建设公司,外贸营销网站建设,网站建设价格女123. 买卖股票的最佳时机 III - 力扣#xff08;LeetCode#xff09; 状态#xff1a;查看索引含义和初始化思路后AC。 增加了两次的限制#xff0c;相应的就是需要考虑的状态改变#xff0c;具体的索引含义在代码中#xff1a;
class Solution {
public:int maxProfit(… 123. 买卖股票的最佳时机 III - 力扣LeetCode 状态查看索引含义和初始化思路后AC。 增加了两次的限制相应的就是需要考虑的状态改变具体的索引含义在代码中
class Solution {
public:int maxProfit(vectorint prices) {int len prices.size();vectorvectorint dp(len, vectorint(5, 0));// dp[i][0] - 无操作// dp[i][1] - 第一次持有// dp[i][2] - 第一次不持有// dp[i][3] - 第二次持有// dp[i][4] - 第二次不持有dp[0][0] 0, dp[0][1] -prices[0], dp[0][2] 0, dp[0][3] -prices[0], dp[0][4] 0;for(int i 1; i len; i){dp[i][1] max(dp[i-1][1], dp[i-1][0]-prices[i]);dp[i][2] max(dp[i-1][2], dp[i-1][1]prices[i]);dp[i][3] max(dp[i-1][3], dp[i-1][2]-prices[i]);dp[i][4] max(dp[i-1][4], dp[i-1][3]prices[i]);}return dp[len-1][4];}
}; 188. 买卖股票的最佳时机 IV - 力扣LeetCode 状态思路正确对k的偶数判断有误。 注意对K的处理和遍历过程中的相对变化代码如下
class Solution {
public:int maxProfit(int k, vectorint prices) {// 就是j的变换从2维度变成5维再变成k维int len prices.size();if(len 0) return 0;vectorvectorint dp(len, vectorint(2*k1, 0));// initialdp[0][0] 0;for(int i 1; i 2*k; i 2){dp[0][i] -prices[0];}for(int i 1; i len; i){for(int j 0; j 2*k-1; j 2){dp[i][j1] max(dp[i-1][j1], dp[i-1][j]-prices[i]);dp[i][j2] max(dp[i-1][j2], dp[i-1][j1]prices[i]);}}return dp[len-1][2*k];}
};
