动态规划中股票买卖一直是高频考点，重点在于区分股票的持有状态和一天内能几次买卖股票，了解这些就不难推导出递推公式。
首先回顾一下动态规划五部曲：
- 1 定义递归数组
- 2 推导递归公式
- 3 初始化递归数组
- 4 确定遍历顺序
- 5 手动打印数组检查是否正确
买卖股票的最佳时机I – 买卖一次
给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。
你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。
返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。
- 1 首先我们需要定义递归数组的含义，如下：dp[i][0]代表第i天持有股票的最大利润，dp[i][1]代表第i天不持有股票的最大利润。
- 2 递归表达式
- 第i天持有股票的最大利润 = 第i-1天持有股票的最大利润+第i-1天不持有股票的最大利润-第i天股票价格
- 第i天不持有股票的最大利润 = 第i-1天不持有股票的最大利润+第i-1天持有股票的最大利润+第i天股票价格
- 3 初始化递归数组
- dp[0][0] = -price[0]
- dp[0][1] = 0
- 4 确定遍历顺序：从左到右
由此可以写出如下代码：
class Solution {
public:
int maxProfit(vector& prices) {
int m = prices.size();
vector<vector> dp(m, vector(2));
dp[0][0] = -prices[0];
dp[0][1] = 0;
for(int i=1; i<m; 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[m-1][1];
}
};
买卖股票的最佳时机II？ – 买卖多次
给你一个整数数组 prices ，其中 prices[i] 表示某支股票第 i 天的价格。
在每一天，你可以决定是否购买和/或出售股票。你在任何时候 最多 只能持有 一股 股票。你也可以先购买，然后在 同一天 出售。
返回 你能获得的 最大 利润 。
- 1 首先我们需要定义递归数组的含义，如下：dp[i][0]代表第i天持有股票的最大利润，dp[i][1]代表第i天不持有股票的最大利润。
- 2 递归表达式
- 第i天持有股票的最大利润 = max(第i-1天持有股票的最大利润, 第i-1天不持有股票的最大利润-第i天股票价格)
- 第i天不持有股票的最大利润 = max(第i-1天不持有股票的最大利润, 第i-1天持有股票的最大利润+第i天股票价格)
- 3 初始化递归数组
- dp[0][0] = -price[0]
- dp[0][1] = 0
- 4 确定遍历顺序：从左到右
需要注意的是，可以买卖多次和买卖一次的区别。
class Solution {
public:
int maxProfit(vector& prices) {
int m = prices.size();
vector<vector> dp(m, vector(2));
dp[0][0] = -prices[0];
dp[0][1] = 0;
for(int i=1; i<m; 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[m-1][1];
}
};
买卖股票的最佳时机 III – 买卖两次
给定一个数组，它的第 i 个元素是一支给定的股票在第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你最多可以完成 两笔 交易。
注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
- 递归数组的含义，dp[i][0]不操作状态，dp[i][1]第i天第一次持有股票的最大利润，dp[i][2]第i天第一次不持有股票的最大利润，dp[i][3]为第i天持第二次持有股票的最大利润，dp[i][4]为第i天第二次不持有股票的最大利润。
- 递归表达式
- 第i天第一次持有股票的最大利润 = max(第i天持有股票的最大利润，不操作 – 第i天股票价格)
- 第i天第一次不持有股票的最大利润 = max(第i天第一次不持有股票的最大利润， 第i-1天持有股票的最大利润+第i天股票价格)
- ……
相比买卖一次、多次，买卖两次其实就是递归数组的定义和递归公式的区别。
class Solution {
public:
int maxProfit(vector& prices) {
int m = prices.size();
vector<vector> dp(m, vector(5, 0));
dp[0][1] = -prices[0];
dp[0][3] = -prices[0];
for(int i=1; i<m; 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[m-1][4];
}
};
买卖股票的最佳时机 IV – 买卖k次
给你一个整数数组 prices 和一个整数 k ，其中 prices[i] 是某支给定的股票在第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你最多可以完成 k 笔交易。也就是说，你最多可以买 k 次，卖 k 次。
注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
与上面同理，需要注意递归数组的定义和递归表达式的处理。
class Solution {
public:
int maxProfit(int k, vector& prices) {
int m = prices.size();
vector<vector> dp(m, vector(2*k+1, 0));
for(int i=1; i<2*k; i=i+2)
{
dp[0][i] = -prices[0];
}
for(int i=1; i<m; i++)
{
for(int j=1; j<=2*k; j++)
{
if (j%2 == 1) dp[i][j] = max(dp[i-1][j], dp[i-1][j-1]-prices[i]);
else dp[i][j] = max(dp[i-1][j], dp[i-1][j-1]+prices[i]);
}
}
return dp[m-1][2*k];
}
};