赞
踩
12-17:笔者最近发现了一个非常不错的算法系列文章:labuladong大神的fucking-algorithm,其中的动态规划部分有一篇专门讲股票买卖问题的解题框架,读完后受益良多,在此推荐给大家:团灭LeetCode股票买卖问题。因此从本文第三题开始,后续的题目都不再提供思路,只给算法的C++实现。
2020-11-08 晴
今天的每日一题是" 122 买卖股票的最佳时机 II "。看了下相似题目,居然有五道类似的题目,再加上之前看 CLRS 时遇到过类似的问题(第四章 分治法 4.1 最大子数组问题),于是便想对这些题目解题思路和方法做个汇总,从题目差异与方法差异中提取一套通用的思考模板(看情况吧,主要是作个汇总,方便以后查阅)。
难度:简单
【问题描述】
【示例】
【思路 I】Brutal Force O(N2) 超时
“万物始于暴力”。尽管很多算法问题单纯使用暴力法是会超时的,但几乎所有闪亮的方法都源于此,清楚如何暴力求解也就成功了一半,因为这表明我们至少已经明确了问题,剩余的工作就是在此基础上分析可优化的部分。
思路很简单, 我们可以用变量 i
表示买入股票的时点, 用变量 j
表示卖出股票的时点,那么 prices[j] - prices[i]
就是股票收益,我们找出最大的即可。
int maxProfit(vector<int>& prices) {
int ans = 0;
for (int i=0; i<prices.size(); ++i)
for (int j=i+1; j<prices.size(); ++j)
ans = max(ans, prices[j] - prices[i]);
return max(0, ans);
}
【时间复杂度】O(N2) 二层循环,且循环内部开销为O(1),因此不难得出为O(N2)。
【空间复杂度】 O(1) 过程中只使用了两个变量用于循环,常量开销。
【思路 II】Divide-and-Conquer O(NLogN)
首先对股票价格后前两两作差得到"利润数组",我们的目的就是从这个数组中找出一段连续的子数组,使得此子数组的元素和最大(而且不能小于0)。这段连续的最大子数组,要么在利润数组的左半边,要么在其右半边,要么跨越左右两边,由此我们可以"分而治之",左、右两半的问题恰好是一个规模减半的子问题,横跨左右两边的情况需要额外处理,最后得到三者中的最大值即为答案。
class Solution { public: int maxProfit(vector<int>& prices) { vector<int> profits; for (int i=1; i<prices.size(); ++i){ profits.push_back(prices[i]-prices[i-1]); } return maxProfit(profits, 0, profits.size()-1); } //分治法 int maxProfit(vector<int>& v, int p, int r){ if(p == r) return v[p] > 0 ? v[p] : 0; else if(p < r){ int mid = (p + r) / 2; int left = maxProfit(v, p, mid); int right = maxProfit(v, mid+1, r); int cross = max_CrossProfit(v, p, mid, r); return max(0, max(left, max(right, cross))); } return 0; } //跨越中界的最大子数组 int max_CrossProfit(vector<int>& v, int p, int mid, int r){ int max_left = 0, max_right = 0; int cur = 0; int i=mid; //left while (i >= p){ cur += v[i--]; max_left = max(max_left, cur); } i = mid+1; cur = 0; //right while (i <= r){ cur += v[i++]; max_right = max(max_right, cur); } return max(0, max_left + max_right); } };
【时间复杂度】O(NLogN) 设原问题的运行时间为T(N),时间开销主要为左右两半子数组的子问题递归(T(N/2))以及横跨数组的非子问题(Θ(N)),列出其运行时间递归式:T(N) = 2T(N/2) + Θ(N),根据主定理可知其符合 情况2
为 Θ(NLogN)。
【空间复杂度】 O(N) 空间开销主要在两个方面:一个是在利润数组 profits
上,为O(N);另一个在分治法递归的系统栈开销,其递归深度满足S(N) = 2S(N/2) + O(1),用主定理可知其符合 情况1
为 Θ(N)。两者叠加仍为线性开销。
【思路 III】非递归的线性时间方法 (Greedy?) O(N)
借用 CLRS 练习4.1-5 的思想,其伪代码如下:
ITERATIVE-FIND-MAXIMUM-SUBARRAY(A)
n = A.length
max-sum = -∞
sum = -∞
for j = 1 to n
if sum > 0
sum = sum + A[j]
else
sum = A[j]
if sum > max-sum
max-sum = sum
return max-sum
下面为其C++实现:
int maxProfit(vector<int>& prices) { vector<int> profits; for (int i=1; i<prices.size(); ++i){ profits.push_back(prices[i]-prices[i-1]); } int maxn = -1; int sum = -1; for (int i=0; i<profits.size(); ++i){ if(sum > 0) sum += profits[i]; else sum = profits[i]; if(sum > maxn) maxn = sum; } return max(0, maxn); }
【时间复杂度】O(N) 两个主要部分:一,预处理阶段的耗时为O(N);二,计算最大利润时采用了一次遍历,循环体内部指令开销为O(1),故总体算法时间为O(N)。
【空间复杂度】O(N) 空间开销主要在预处理获得利润数组 profits
上面,为O(N)。
当然我们也可以不做预处理,从而把空间开销降为O(1),为此我们只需要去掉预处理过程,将上述代码中的 profits[i]
替换为 prices[i] - prices[i-1]
,并令 i
从 1
开始即可,在此就不再铺代码了。
12-17【补充思路】DP
class Solution {
public:
int maxProfit(vector<int>& prices) {
int n = prices.size();
int dp_i_0 = 0, dp_i_1 = INT_MIN;
for (int i=0; i<n; ++i){
int temp = dp_i_0;
dp_i_0 = max(dp_i_0, dp_i_1 + prices[i]);
dp_i_1 = max(dp_i_1, -prices[i]);
}
return dp_i_0;
}
};
难度:简单
【问题描述】
【示例】
【问题分析】问题描述的差异
与第一个问题基本一致,主要的不同在于买卖的次数。第一题仅能买卖 1
次,而本题可以多次买卖。它们带来的差异可以拿 示例1
来分析,在 示例1
中,一次购买的最大收益为 [1, 6]
,即为 5
;多次购买的最大收益为 [1, 5]
、[3, 6]
,共 2
次买卖,即为 7
。其实放在实际生活中,我们大多会采取类似第二题所描述的方式买卖股票,即进行多次购入和售出,因为未来的走势是不确定的,我们当然倾向于在价格达到顶峰时将之抛售,倘若想通过一次购买获得最大利润,我们往往需要忍受股票"缩水"带来的痛苦,需要有足够的耐心去等待股票价格的上涨,这显然是风险更大的一种举措。
从上面的例子进一步分析,似乎看到了两者的核心差异——是否要让手中的股票经历"贬值"的时期。前者是,后者否。我们可以把第一个问题看作是第二个问题的"子问题",即我们要求多次购买中的每一次购买都是最大收益的,局部最优解之和必定是全局最优解,因为子问题之间互不干扰,由此我们可以采用贪心算法解决此问题。
【思路】Greedy
贪心使得我们总想着在价格最低时购入股票,在价格最高时抛出,如此往复。下面是我最初构想的代码,详细地模拟了上面描述的过程,会有些繁琐,也正因如此我WA了3次才通过(我是菜b)。
int maxProfit(vector<int>& prices) { int maxn = 0; int stock_in = prices[0]; //购入股票时的价格 int stock_out; //售出股票时的价格 bool toBuy = true; //表示是购买状态(true)还是抛售状态(false) for (int i=1; i<prices.size(); ++i){ if(toBuy){ //购买状态 if(stock_in >= prices[i]) stock_in = prices[i]; else{ //可能会抛出 toBuy = false; stock_out = prices[i]; if(i == prices.size()-1) //最后一天达到顶峰 maxn += max(0, stock_out - stock_in); } } else{ //抛售状态 if(stock_out <= prices[i]){ //可能会抛出 stock_out = prices[i]; if(i == prices.size()-1)//最后一天达到顶峰 maxn += max(0, stock_out - stock_in); } else{ //一定会抛出 toBuy = true; //累计 maxn += max(0, stock_out - stock_in); stock_in = prices[i]; } } } return maxn; }
【时间复杂度】O(N)
【空间复杂度】 O(1)
一种 “cleaner” 的写法
int maxProfit(vector<int>& prices) {
int maxn = 0;
for (int i=1; i<prices.size(); ++i)
maxn += max(0, prices[i]-prices[i-1]);
return maxn;
}
【时间复杂度】O(N)
【空间复杂度】 O(1)
上述代码可以这么理解:设 x = prices[i]-prices[i-1]
,当x < 0
时果断不买,并且prices[i]
成为了我们的"待购目标",所谓"代购目标"指的是我们可能会买入的股票,但因为我们不确定还有更低价格的时点,因此暂不购入,这个最低价格股票的购买过程隐含在了x < 0
时的每一轮迭代步骤中;当x >= 0
时我们"假定出售",从而"假定获得利益",所谓"假定"即我们不真正把股票抛售出去,如果股票价格还在涨,直到要下降时(x < 0
),我们之前的所有加和可以看作这一次买卖的收益,如此往复。
12-17【补充思路】DP
class Solution {
public:
int maxProfit(vector<int>& prices) {
// dp[i][k][0] = max(dp[i-1][k][0], dp[i-1][k][1] + prices[i]);
// dp[i][k][1] = max(dp[i-1][k][1], dp[i-1][k-1][0] - prices[i]); k-> inf => k-1 == k
int n = prices.size();
int dp_i_0 = 0, dp_i_1 = INT_MIN;
for (int i=0; i<n; ++i){
int temp = dp_i_0;
dp_i_0 = max(dp_i_0, dp_i_1 + prices[i]);
dp_i_1 = max(dp_i_1, temp - prices[i]);
}
return dp_i_0;
}
};
2020-12-17 晴
一个月了,今天的每日一题是含手续费的股票买卖问题,于是乎就想起了搁置一个多月的这篇文章。碰巧的是,今天正好看到了labuladong大神的手撕算法之团灭LeetCode股票买卖问题。该文章提取了股票买卖问题的通用框架,并给出了解决动态规划问题的一般步骤,笔者从中受益良多。因此对于后续题目的思路,笔者就不再赘述,需要的可以读上面给的文章。笔者下面主要是依照那篇文章提供的思维框架,给出 C++ 的具体实现。
难度:困难
【问题描述】
【代码】
class Solution { public: int maxProfit(vector<int>& prices) { // k = 2 // dp[i][k][0] = max(dp[i-1][k][0], dp[i-1][k][1] + prices[i]); // dp[i][k][1] = max(dp[i-1][k][1], dp[i-1][k-1][0] - prices[i]); // baseCase: dp[0][k][0] = 0, dp[0][k][1] = -inf dp[i][0][0 or 1] = 0 int n = prices.size(); int dp[n+1][3][2]; // init when k=0 for (int i=0; i<n; ++i) for (int j=0; j<2; ++j) dp[i][0][j] = 0; dp[0][1][0] = dp[0][2][0] = 0; dp[0][1][1] = dp[0][2][1] = INT_MIN; for (int i=1; i<=n; ++i){ for (int k=1; k<=2; ++k){ dp[i][k][0] = max(dp[i-1][k][0], dp[i-1][k][1] + prices[i-1]); dp[i][k][1] = max(dp[i-1][k][1], dp[i-1][k-1][0] - prices[i-1]); } } return dp[n][2][0]; } };
【注意】
之前做的题目要么是最多一次,要么是无限制,那些情况下不需要考虑交易次数这个状态,此题交易两次,因此有必要考虑交易次数这一状态,注意初始情况要写全写对(见注释),而且这里第一维度从0开始,0代表第一天之前,在初始情况中进行处理。
【时间复杂度】 O(N)
【空间复杂度】 O(N)
难度:困难
【问题描述】
【代码】
class Solution { public: int maxProfit(int k, vector<int>& prices) { int n = prices.size(); if(k > n / 2 ) k = n / 2; int dp[n+1][k+1][2]; // base case dp[i][0][0 or 1] = 0, dp[0][k][0] = 0, dp[0][k][1] = -inf for (int i=0; i<=n; ++i) for (int j=0; j<2; ++j) dp[i][0][j] = 0; for (int i=1; i<=k; ++i){ dp[0][i][0] = 0; dp[0][i][1] = INT_MIN; } for (int i=1; i<=n; ++i){ for (int j=1; j<=k; ++j){ dp[i][j][0] = max(dp[i-1][j][0], dp[i-1][j][1] + prices[i-1]); dp[i][j][1] = max(dp[i-1][j][1], dp[i-1][j-1][0] - prices[i-1]); } } return dp[n][k][0]; } };
【注意】
注意这里的 k 的范围很大,如果不进行空间压缩是行不通的,需要注意的是,对于 n 天的买卖问题,最多能进行 n/2 笔交易,这道题来说也就是最多 500 笔交易,这个规模申请空间是可行的。考虑了这点后,后续的步骤与第123题类似。
【时间复杂度】 O(n × min(n/2, k))
【空间复杂度】 O(n × min(n/2, k))
难度:中等
【问题描述】
【代码1】 原始DP
d p [ i ] [ k ] → 第 一 维 : 第 i 天 ; 第 二 维 : 0 − 持 有 股 票 1 − 未 持 股 票 且 在 冷 冻 期 2 − 未 持 股 票 且 不 在 冷 冻 期 dp[i][k] \rightarrow 第一维:第 i 天;第二维:0-持有股票\quad1-未持股票且在冷冻期 \quad2-未持股票且不在冷冻期 dp[i][k]→第一维:第i天;第二维:0−持有股票1−未持股票且在冷冻期2−未持股票且不在冷冻期
class Solution { public: int maxProfit(vector<int>& prices) { int n = prices.size(); int dp[n+1][3]; // 0-hold 1-not hold and in cooldown 2-not hold and not in cooldown //base case dp[0][0] = dp[0][1] = -inf, dp[0][2] = 0 dp[0][0] = dp[0][1] = INT_MIN; dp[0][2] = 0; for (int i=1; i<=n; ++i){ dp[i][0] = max(dp[i-1][0], dp[i-1][2] - prices[i-1]); dp[i][1] = dp[i-1][0] + prices[i-1]; dp[i][2] = max(dp[i-1][2], dp[i-1][1]); } return max(dp[n][1], dp[n][2]); } };
【时间复杂度】 O(N)
【空间复杂度】 O(N)
【代码2】 DP空间优化
class Solution { public: int maxProfit(vector<int>& prices) { int n = prices.size(); // 0-hold 1-not hold and in cooldown 2-not hold and not in cooldown //base case dp[0][0] = dp[0][1] = -inf, dp[0][2] = 0 int dp_i_0 = INT_MIN, dp_i_1 = INT_MIN, dp_i_2 = 0; for (int i=0; i<n; ++i){ int temp1 = dp_i_0; int temp2 = dp_i_1; dp_i_0 = max(dp_i_0, dp_i_2 - prices[i]); dp_i_1 = temp1 + prices[i]; dp_i_2 = max(dp_i_2, temp2); } return max(dp_i_1, dp_i_2); } };
【时间复杂度】 O(N)
【空间复杂度】 O(1)
难度:中等
【问题描述】
【代码】
class Solution { public: int maxProfit(vector<int>& prices, int fee) { // State: 持有股票 1 /没有股票 0 | 第 i 天 // dp[i][0 or 1] -> 第 i 天 持有股票/没持股票的最大利润,且 dp[i][0] > dp[i][1] // STE // dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i] - fee); // dp[i][1] = max(dp[i-1][1], dp[i-1][0] - prices[i]); // baseCase: dp[-1][1] = -inf, dp[-1][0] = 0 // ans: dp[n-1][0] int n = prices.size(); int dp_i_0 = 0, dp_i_1 = INT_MIN; for (int i=0; i<n; ++i){ int temp = dp_i_0; dp_i_0 = max(dp_i_0, dp_i_1 + prices[i]); dp_i_1 = max(dp_i_1, temp - prices[i] - fee); } return dp_i_0; } };
【注意】
这里原则上来说把手续费扣在买入或卖出都是没问题的,但在上述代码中,如果将手续费在卖出时计算,则有可能会存在整数下界溢出,需要数值或代码的调整。
【时间复杂度】 O(N)
【空间复杂度】 O(1)
最后总结一下这类题(动态规划)的基本解题步骤:
穷举状态,从而确定维数 (定义DP)
列出状态转移方程,阐明状态变化的递推关系 (写出STE)
确定初始情况 (Base Case) 和目标状态
写代码,注意循环迭代的顺序。例如,对于二维DP Table,可能从左到右,或者从右到左,或者从左上到右下,或者左下到右上等等。
考虑状态压缩与优化
由于笔者个人水平有限,难免会存在笔误或思路描述上的错误(或其他未知错误),望各位大佬们谅解,也欢迎各位大佬们批评指正!(我已经做好立正挨打的准备了~QAQ)
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。