代码随想录算法训练营 ---第五十天

第一题：

简介：

做买卖股票的问题最重要的是分析状态，将状态分析清楚本题也就做出来了。我们看本题它说我们至多可以完成两笔交易，也就意味着我们有两种选择

dp状态分析

1.完成一次交易获得最大利益

  完成一次交易我们用二维数组来因为完成一次交易有两个状态，dp[i][0](第一次持股票最大利益)  和  dp[i][1] （第一次不持股票的最大利益）

2.完成两次交易夺得最大利益

    完成两次交易那我们就有四个状态分别是

dp[i][1]

第一次持有股票

dp[i][2]

第一次不持有股票

dp[i][3]

第二次持有股票

dp[i][4]

第二次不持有股票

状态分析完成后我们看状态转移方程

达到dp[i][1]状态，有两个具体操作：

操作一：第i天买入股票了，那么dp[i][1] = dp[i-1][0] - prices[i]操作二：第i天没有操作，而是沿用前一天买入的状态，即：dp[i][1] = dp[i - 1][1]

所以 dp[i][1] = max(dp[i-1][0] - prices[i], dp[i - 1][1]);

同理dp[i][2]也有两个操作：

操作一：第i天卖出股票了，那么dp[i][2] = dp[i - 1][1] + prices[i]操作二：第i天没有操作，沿用前一天卖出股票的状态，即：dp[i][2] = dp[i - 1][2]

所以dp[i][2] = max(dp[i - 1][1] + prices[i], dp[i - 1][2])

同理可推出剩下状态部分：

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]);

初始化dp数组

第0天没有操作，这个最容易想到，就是0，即：dp[0][0] = 0;

第0天做第一次买入的操作，dp[0][1] = -prices[0];

第0天做第一次卖出的操作，大家可以理解当天买入，当天卖出，所以dp[0][2] = 0;

第0天第二次买入操作，基于第一次卖出后 再买入初始化为：dp[0][3] = -prices[0];

第0天做第二次卖出的操作，大家可以理解当天第二次买入，当天第二次卖出，第二次卖出初始化dp[0][4] = 0;

确定遍历顺序

 因为是依赖dp[i-1]所以从前向后遍历

遍历dp数组看是否符合预期

大家可以看到红色框为最后两次卖出的状态。

现在最大的时候一定是卖出的状态，而两次卖出的状态现金最大一定是最后一次卖出。如果想不明白的录友也可以这么理解：如果第一次卖出已经是最大值了，那么我们可以在当天立刻买入再立刻卖出。所以dp[4][4]已经包含了dp[4][2]的情况。也就是说第二次卖出手里所剩的钱一定是最多的。

所以最终最大利润是dp[4][4]

代码实现： class Solution { public: int maxProfit(vector& prices) { if (prices.size() == 0) return 0; vector> dp(prices.size(), vector(5, 0)); dp[0][1] = -prices[0]; dp[0][3] = -prices[0]; for (int i = 1; i < prices.size(); i++) { dp[i][0] = dp[i - 1][0]; 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]); } for(int i=0;i

简介：

本题和上一题的区别在于可以交易k次状态，所以我们有2*k+1个状态。然后我们可以看一下上一题我分析的两次交易数量不同，状态转移方程的不同发现一下其中的规律就可以做了。

代码实现：  class Solution { public: int maxProfit(int k, vector& prices) { if (prices.size()<2) return 0; vector> dp(prices.size(), vector(2*k+1,0)); for(int i=1;i    今天和昨天都是股票买卖的问题，经过这两天的学习，发现了此系列的规律，继续加油！