力扣 | 动态规划 | 状态机 | 买卖股票 | 买卖股票的最佳时机
文章目录
- 一、309. 买卖股票的最佳时机含冷冻期
- 二、714. 买卖股票的最佳时机含手续费
- 三、123. 买卖股票的最佳时机 III
- 四、188. 买卖股票的最佳时机 IV
本质上这种属于动态规划题目但又有多种状态的,我们只需要正确定义出状态即可。可能每个人定义的状态不一样,但只要是对的就行。
一、309. 买卖股票的最佳时机含冷冻期
LeetCode:309. 买卖股票的最佳时机含冷冻期
个人思路分析:
这个题还蛮不容易的其实,线性dp直接做一维肯定不行,因为对于任何一个股票价格它的状态太多了,不知道何时是买入,不知道有没有买入,你怎么定义dp都无法很好的转移。 那么我们能做的就是给每个价格一个状态,我们分析一下都有哪些状态呢?
- 本次是买入:
dp[i][0]
- 本次是卖出:
dp[i][1]
- 已经有买入,本次不卖不买:
dp[i][2]
- 没有买入,本次不卖不买:
dp[i][3]
一共三个状态,我们尝试使用 d p [ i ] [ 0 ] dp[i][0] dp[i][0] ~ d p [ i ] [ 3 ] dp[i][3] dp[i][3] 来表示这三个状态,他们的转移方程为:
dp[i][0] = dp[i - 1][3] - prices[i]
(前一天不能卖出,也不能已经买入过了)dp[i][1] = max(dp[i - 1][0], dp[i - 1][2]) + prices[i]
dp[i][2] = max(dp[i - 1][2], dp[i - 1][0])
dp[i][3] = max(dp[i - 1][3], dp[i - 1][1])
时间复杂度: O ( n ) O(n) O(n)
class Solution {
public:int maxProfit(vector<int>& prices) {int n = prices.size();if(n == 1) return 0;vector<vector<int>> dp(n, vector<int>(4, 0));//dp[i][0]表示买入第i个、dp[i][1]表示卖出的最大受益dp[1][0] = -prices[1];dp[1][1] = prices[1] - prices[0];dp[1][2] = -prices[0];dp[1][3] = 0;for(int i = 2; i < n; ++ i){dp[i][0] = dp[i - 1][3] - prices[i];//(前一天不能卖出,也不能已经买入过了)dp[i][1] = max(dp[i - 1][0], dp[i - 1][2]) + prices[i];dp[i][2] = max(dp[i - 1][2], dp[i - 1][0]);dp[i][3] = max(dp[i - 1][3], dp[i - 1][1]);}return max(dp[n - 1][1], dp[n - 1][3]);}
};
当然使用滚动数组也是可以优化空间的,这里不做过多解释。
官解思路的本质:
如果说,纯个人思考的思路是:我今天干什么,转移的思路是怎么样我今天才能这样干
那么官解的思路是:今天操作后的状态的是什么,转移的思路是怎么样我今天之后是这样一个状态
官解状态,实际上去思考今天后的状态可能是哪些:
- 手里有股票
- 手里没股票
- 冷冻期
- 非冷冻期
其实知道状态后就很容易做了,不过你要怎么去思考完全看你自己如何定义状态,你可以定义今天过后,也可以定义今天干什么,无论如何都要把今天的影响代入,只要状态足以解决问题就够了。
二、714. 买卖股票的最佳时机含手续费
LeetCode:714. 买卖股票的最佳时机含手续费
这个题和之前那个题不同之处在于,这里没有冷冻时间,那么相应的状态也会发生变化。
如果考虑今天之后的状态,则状态可以是:
- 持有股票
- 不持有股票
一共两种状态。
如果考虑今天做什么,则状态可以是:
- 买股票
- 卖出股票
- 持有股票,但什么都不做
- 不持有股票,但什么都不做
一共四种状态。
我们选择今天之后的状态,定义 d p [ i ] [ 0 ] dp[i][0] dp[i][0] ~ d p [ i ] [ 1 ] dp[i][1] dp[i][1],则有状态转移:
dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] - prices[i])
(持有股票)dp[i][1] = max(dp[i - 1][0] + prices[i] - fee, dp[i - 1][1])
时间复杂度: O ( n ) O(n) O(n)
可降低空间复杂度为: O ( 1 ) O(1) O(1)
class Solution {
public:int maxProfit(vector<int>& prices, int fee) {vector<array<int, 2>> dp((int) prices.size(), array<int, 2>{});dp[0][0] = -prices[0], dp[0][1] = 0; for(int i = 1; i < (int) prices.size(); ++ i){dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] - prices[i]);dp[i][1] = max(dp[i - 1][0] + prices[i] - fee, dp[i - 1][1]);}return dp[(int) prices.size() - 1][1];}
};
本题还能用贪心解决,在股票低谷买入,股票高峰卖出,且保证不亏的时候才进行这个操作。实际上就是摆动序列,在下坡或上坡的时候的差值之和 才能达到 股票高峰 和 股票低谷的差值,所以我们只需要考虑高峰低谷点即可。
三、123. 买卖股票的最佳时机 III
LeetCode:123. 买卖股票的最佳时机 III
本题不能直接用贪心,因此这不是无限次购买,只能买两次,因此如果每次都贪,会导致局部最优不是全局最优。
那么做出这道题实际上,我们只需要理解状态机本质就可以。
可以定义今天之后的状态:
- 持有一张股票,未进行过买卖
- 持有一张股票,进行过一次买卖
- 不持有股票,进行过一次买卖
- 不持有股票,进行过两次买卖
- 不持有股票,未进行过买卖 (直接将这个状态的值写为0即可)
状态可以定义为 d p [ i ] [ 0 ] dp[i][0] dp[i][0] ~ d p [ i ] [ 4 ] dp[i][4] dp[i][4] ,转移方程为:
dp[i][0] = max(dp[i - 1][0], 0 - prices[i])
dp[i][1] = max(dp[i - 1][1], dp[i - 1][2] - prices[i])
dp[i][2] = max(dp[i - 1][2], dp[i - 1][0] + prices[i])
dp[i][3] = max(dp[i - 1][3], dp[i - 1][1] + prices[i])
对于第0
天的情况,如果你认为可以当天买入且卖出,那么dp[0][2] = dp[0][3] = 0;
;如果你认为这种情况不存在,那么令这两个的受益为负无穷,即这种情况不予考虑。
class Solution {
public:int maxProfit(vector<int>& prices) {int n = prices.size();vector<array<int, 4>> dp(n, array<int, 4>{});dp[0][0] = -prices[0], dp[0][1] = -0x3f3f3f3f;dp[0][2] = -0x3f3f3f3f, dp[0][3] = -0x3f3f3f3f;for(int i = 1; i < n; ++ i){dp[i][0] = max(dp[i - 1][0], - prices[i]);dp[i][1] = max(dp[i - 1][1], dp[i - 1][2] - prices[i]);dp[i][2] = max(dp[i - 1][2], dp[i - 1][0] + prices[i]);dp[i][3] = max(dp[i - 1][3], dp[i - 1][1] + prices[i]);}return max(0, max(dp[n - 1][2], dp[n - 1][3]));}
};
同上,空间优化就不做了。
四、188. 买卖股票的最佳时机 IV
LeetCode:188. 买卖股票的最佳时机 IV
这个题通过状态机转换可以知道,如果我们定义多个状态实际上就能解决。
- 定义 d p [ i ] [ 0 ] dp[i][0] dp[i][0]表示今天之后持有一张股票,未进行过买卖
- 定义 d p [ i ] [ 1 ] dp[i][1] dp[i][1]表示今天之后不持有股票,进行过一次买卖
- 定义 d p [ i ] [ 2 ] dp[i][2] dp[i][2]表示今天之后持有一张股票,进行过一次买卖
- 定义 d p [ i ] [ 3 ] dp[i][3] dp[i][3]表示今天之后不持有股票,进行过两次买卖
- ···
class Solution {
public:int maxProfit(int k, vector<int>& prices) {int n = prices.size();vector<vector<int>> dp(n, vector<int>(2 * k, -0x3f3f3f3f));dp[0][0] = -prices[0];for(int i = 1; i < n; ++ i){dp[i][0] = max(dp[i - 1][0], -prices[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 max(0, *max_element(dp[n - 1].begin(), dp[n - 1].end()));}
};
内存优化一下吧,非常简单
class Solution {
public:int maxProfit(int k, vector<int>& prices) {int n = prices.size();int m = 2 * k;vector<int> dp(m, -0x3f3f3f3f);dp[0] = -prices[0];for(int i = 1; i < n; ++ i){dp[0] = max(dp[0], -prices[i]);for(int j = 1; j < m; ++ j){if(j % 2 == 1){dp[j] = max(dp[j], dp[j - 1] + prices[i]);}else{dp[j] = max(dp[j], dp[j - 1] - prices[i]);}}}return max(0, *max_element(dp.begin(), dp.end()));}
};