大家好，今天是我们的算法训练营的第四十四天，今天我们还是继续讲解我们的动态规划章节，前几天我们主要讲解的是背包问题，包括了0-1背包，完全背包，还有比较著名的打家劫舍问题，那么今天我们就继续我们的动态规划章节，今天的题目依旧是动态规划章节里面比较典型的题目。我们一定要拿下这些题目。
第一题对应力扣编号为121的题目买卖股票的最佳时机
这是我们今天的第一道题目，其实综合我们以前在动态规划章节刷过的题目，这道题目虽说换了一个名字会不会还是背包问题的变式题呢？我们先一起来看一下题目：
其实题目要求很简单，我们最后要获得最大利润的话，很明显就是我们要在股票价格最低的时候买进股票，股票价格最高的时候卖出股票，这样就可以保证我们的利润是最大的，其实我们可以不用动态规划算法也可以解决这道题目，我们就首先使用贪心算法来解决试一下：
class Solution {
public:
int maxProfit(vector<int>& prices) {
int low = INT_MAX;
int result = 0;
for (int i = 0; i < prices.size(); ++i)
{
low = min(low, prices[i]);
result = max(result, prices[i] - low);
}
return result;
}
};这是本道题目使用贪心算法的解题代码，在这里我就不解释贪心算法的思路了，我们还是重点看一下我是用动态规划的思路应该如何解决这道题目：当然毫无疑问我们肯定是需要使用动规五部曲，
第一步就是确定dp数组（dp table）以及下标的含义，dp[i][0] 表示第i天持有股票所得最多现金，这个其实是很有必要的，如果我们买了股票的话那目前我们持有的现金就是-prices[i], dp[i][1] 表示第i天不持有股票所得最多现金，这个有点抽象，注意这里说的是“持有”，“持有”不代表就是当天“买入”！也有可能是昨天就买入了，今天保持持有的状态，这里一定要分清楚。
第二步就是确定递推公式，如果第i天持有股票即dp[i][0]， 那么可以由两个状态推出来，第i-1天就持有股票，那么就保持现状，所得现金就是昨天持有股票的所得现金 即：dp[i - 1][0]，也就是说股票并不是今天买来的，只不过今天我不想买我觉得今天的股票价值不够高，还有一种情况就是第i天买入股票，所得现金就是买入今天的股票后所得现金即：-prices[i]，这样的话dp[i][0]应该选所得现金最大的，所以dp[i][0] = max(dp[i - 1][0], -prices[i]); 如果第i天不持有股票即dp[i][1]， 也可以由两个状态推出来，第一种就是第i-1天就不持有股票，那么就保持现状，所得现金就是昨天不持有股票的所得现金 即：dp[i - 1][1]，还有一种情况就是第i天卖出股票，所得现金就是按照今天股票价格卖出后所得现金即：prices[i] + dp[i - 1][0]，同样dp[i][1]取最大的，dp[i][1] = max(dp[i - 1][1], prices[i] + dp[i - 1][0])，截止到现在我们就分析完了我们的递推公式。
第三步就是dp数组的初始化，我们看我们的递推公式我们会发现基础都是要从dp[0][0]和dp[0][1]推导出来，那么dp[0][0]表示第0天持有股票，此时的持有股票就一定是买入股票了，因为不可能有前一天推出来，所以dp[0][0] -= prices[0]; dp[0][1]表示第0天不持有股票，不持有股票那么现金就是0，所以dp[0][1] = 0，这个初始化并不难理解，有一个问题就是大家得搞明白我们持有股票和今天买来股票的区别。
第四步就是确定遍历顺序，这个毫无疑问，就是从前往后遍历，因为我们后面的状态都是由前面推导出来的。
在这里我要说明一下我们dp数组的含义，大家很容易出现一种误区就是我表示的就是我当天就必须买股票或者卖股票，但其实这样是不对的，我们应该是持有的状态才对，我上面解释过我们可能第i-1天就已经买出或者卖出股票了，只不过我现在保持着这种买入或者卖出的状态而已，最后我们所有的日子过完了我们才可以得到我们的最大的利润。
这样我们就可以尝试给出这道题目的解题代码：
class Solution {
public:
int maxProfit(vector<int>& prices) {
int len = prices.size();
if (len == 0) return 0;
//定义dp数组
vector<vector<int>> dp(len, vector<int>(2));
//初始化dp数组
dp[0][0] = -prices[0];
dp[0][1] = 0;
//状态转移
for (int i = 1; i < len; ++i)
{
dp[i][0] = max(dp[i - 1][0], -prices[i]);
dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] + prices[i]);
}
return dp[len - 1][1];
}
};大家一定要注意我们的状态转移，不要搞错。 dp[i][1]表示的是在第i天不持有股票的状态，那我其实可以继续保持这个持有股票的状态，当然也可以在第i天把股票卖了，这样我也是不持有股票的状态，但注意我们前一天就肯定是持有股票的状态，我们卖了就得再加上prices[i]就可以了。还有一个问题就是本题中不持有股票状态所得金钱一定比持有股票状态得到的多，所以最后我输出的不是dp[len-1][0]这点要了解。
第二题对应力扣编号为122的题目买卖股票的最佳时机II
这一道题目应该是我们上一道题目的变式题，我们来看一下与上一道题目有什么不一样的地方：
这道题目以前应该是做过，可能是在贪心算法章节做过，这道题目其实是我的买卖股票的次数不限制了，我们上一道题目是只能有一次股票买卖的机会，那其实本道题目有一个非常简单的暴力算法我们会一直累加，只要可以保证卖的时候股票价格大于买的时候股票价格就可以，我给出大家暴力解法的代码：
class Solution {
public:
int maxProfit(vector<int>& prices) {
int result = 0;
for (int i = 1; i < prices.size(); ++i)
{
result += max(0, prices[i] - prices[i - 1]);
}
return result;
}
};那我们主要还是看动态规划的思路，其实我们dp数组的定义与初始化与上一道题目是完全一样的这里我就不说了，与上一道题目不一样的地方就是推导dp[i][0]的时候，第i天买入股票的情况。在本题里因为一只股票可以买卖多次，所以当第i天买入股票的时候，所持有的现金可能有之前买卖过的利润。其实我们也可以想清楚这道题目是可以随时买随时卖的，所以我们可能在第 i-1天就卖过一次，所以这时候可能就会有利润了，那么第i天持有股票即dp[i][0]，如果是第i天买入股票，所得现金就是昨天不持有股票的所得现金 减去 今天的股票价格 即：dp[i - 1][1] - prices[i]。还有如果第i天不持有股票即dp[i][1]的情况，第i-1天就不持有股票，那么就保持现状，所得现金就是昨天不持有股票的所得现金 即：dp[i - 1][1]，保持了原状态，还有第i天卖出股票，所得现金就是按照今天股票价格卖出后所得现金即：prices[i] + dp[i - 1][0]。这样我们就可以给出代码:
class Solution {
public:
int maxProfit(vector<int>& prices) {
int len = prices.size();
vector<vector<int>> dp(len, vector<int>(2));
dp[0][0] = -prices[0];
dp[0][1] = 0;
for (int i = 1; i < len; ++i)
{
//如果是第i天买入股票，所得现金就是昨天不持有股票的所得现金 减去 今天的股票价格
dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] - prices[i]);
dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] + prices[i]);//不持有股票可以是上面状态的延续也可以是今天卖出股票这样前面一天
//一定是持有股票
}
return dp[len - 1][1];
}
};第三题对应力扣编号为123的题目买卖股票的最佳时机III
这是我们今天的最后一道题目，这道题目应该是很有难度的，我们还是先看一下题目要求：
这道题的意思是我们最多可以完成两笔交易，而且只能买一次卖一次，不能连续买两次然后再卖，那这样其实就很困难了，关键在于至多买卖两次，这意味着可以买卖一次，可以买卖两次，也可以不买卖。当然我们还是会使用动态规划的思路来解决问题，
第一步还是确定dp数组以及下标的含义，那一天一共就有四个状态，第一次持有股票，第一次不持有股票，第二次持有股票，第二次不持有股票，那我们就这样定义dp[i][j]中 i表示第i天，j为 [0 - 4] 五个状态，dp[i][j]表示第i天状态j所剩最大现金。当然最后要取最大值。还是我们这里还是强调状态并非是第i天买卖股票，这点大家不要误解。
第二步就是确定递推公式，这个估计很难，要达到dp[i][1]状态，有两个具体操作：第一种是第i天买入股票了，那么dp[i][1] = dp[i-1][0] - prices[i]，第二种是第i天没有操作，而是沿用前一天买入的状态，即：dp[i][1] = 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数组的初始化，第0天没有操作，这个最容易想到，就是0，即：dp[0][0] = 0;第0天做第一次买入的操作，dp[0][1] = -prices[0];但是第0天做第一次卖出的操作，这个初始值应该是多少呢？这个很有意思，其实就是当天买入当天卖出，不就是0嘛？股票的价格一天之内不会变，第0天第二次买入操作，初始值应该是多少呢？怎么可能会有这种情况出现，其实第二次买入依赖于第一次卖出的状态，其实相当于第0天第一次买入了，第一次卖出了，然后再买入一次（第二次买入），那么现在手头上没有现金，只要买入，现金就做相应的减少。同理第二次卖出初始化dp[0][4] = 0。
第四步就是确定遍历顺序，从递归公式其实已经可以看出，一定是从前向后遍历，因为dp[i]，依靠dp[i - 1]的数值。
最后我们就给出代码：
class Solution {
public:
int maxProfit(vector<int>& prices) {
if (prices.size() == 0) return 0;
vector<vector<int>> dp(prices.size(), vector<int>(5, 0));
//dp数组的初始化我在前面讲过了
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]);
}
return dp[prices.size() - 1][4];
}
};今日总结
今天的题目我感觉对于第一次做的同学可能难度比较大，尤其是最后一道题目，我们只要遵循动规五部曲就可以，当然我们一定得理解状态转移，这个对于我们解题十分关键，好的，我们今天的分享就到这里，我们明天再见！