[Hdp] lc188. 买卖股票的最佳时机 IV(状态机模型dp+线性dp+空间优化)
1. 题目来源
2. 题目说明
3. 题目解析
该股票问题:最多进行 k 笔交易,每笔交易不能重叠(指买入下支股票前需要将手中股票卖出)
股票问题四部曲:
[Edp] lc121. 买卖股票的最佳时机(dp)
[Edp] lc122. 买卖股票的最佳时机 II(dp+思维)
[Hdp] lc123. 买卖股票的最佳时机 III(dp+前后缀分解)
[Hdp] lc188. 买卖股票的最佳时机 IV(状态机模型dp+线性dp+空间优化)
前后缀分解,在该问题无法再继续应用。
dp
在这求取 k
次交易的最大收益情况。
注意: 这是个困难的 dp
问题
方法一:状态机模型dp
思路:
-
特判,如果 k ≥ n 2 k\ge \frac n 2 k≥2n 那么这就相当于交易无限次,那么就可以采用 [Edp] lc122. 买卖股票的最佳时机 II(dp+思维) 来进行求解了,求每个正区间累加即可
-
考虑一次交易所经历的阶段:
- 第一阶段:买入股票还没卖出
- 第二阶段:卖出股票
-
状态机定义: 用 0 表示交易完,所有手里没股票的状态,1 表示所有没交易完,手里有股票还没卖的状态
-
状态机起点: 第一天手里没有股票,走向状态 0
-
状态 0 分析: 如果我们不买股票,那么手里依旧没有股票,则状态转移从状态 0 转移到状态 0,且当前总钱数未发生改变,+0。同理,也可以买入股票,状态转移从状态 0 转移到状态 1,则表示我们买入股票,则当前总钱数需要
-wi
-
状态 1 分析: 如果我们不买股票,那么手里依旧没有股票,则状态转移从状态 1 转移到状态 1,且当前总钱数未发生改变,+0。同理,也可以卖出股票,状态转移从状态 1 转移到状态 0,则表示我们卖出股票,则当前总钱数需要
+wi
-
状态机终点: 状态机终点一定在手里没有股票的情况
-
最多交易
k
次: 等价于在两个状态之间最多只能转k
次 -
问题转化为从起点出发最多转
k
圈的最大收益 -
状态表示:
-
f[i][j]
表示第i
天交易了j
次股票,且当天不持有股票的最大收益 -
g[i][j]
表示第i
天交易了j
次股票,且当天持有股票的最大收益
-
-
状态初始化:
-
f[0][0] = 0
, 其余均为-inf
-
-
状态转移:
f[i][j] = max(f[i - 1][j], g[i - 1][j] + w[i])
g[i][j] = max(g[i - 1][j], f[i - 1][j - 1] - w[i])
总结: 这个问题超出我的能力范围了,考察了空间优化…即便总结完毕也只是勉强理解,搞不太懂,近期会刷大量的 dp
模板题及变种题,关于股票问题还会二刷补充。届时会根据状态机模型 dp
在算法专栏中进行分类刷题。
已经过不了的代码:
// 数据更新,十分卡常
class Solution {
public:
const int INF = 1000000000;
int maxProfitII(vector<int>& prices) {
int n = prices.size();
int f = 0, g = -INF;
for (int i = 0; i < n; i++) {
int last_f = f, last_g = g;
f = max(last_f, last_g + prices[i]);
g = max(last_g, last_f - prices[i]);
}
return f;
}
int maxProfit(int k, vector<int>& prices) {
int n = prices.size();
if (k >= n / 2)
return maxProfitII(prices);
vector<vector<int>> f(2, vector<int>(k + 1, -INF));
vector<vector<int>> g(2, vector<int>(k + 1, -INF));
f[0][0] = 0;
for (int i = 1; i <= n; i++)
for (int j = 0; j <= k; j++) {
f[i & 1][j] = f[i - 1 & 1][j];
g[i & 1][j] = max(g[i - 1 & 1][j], f[i - 1 & 1][j] - prices[i - 1]);
if (j > 0) // 可以一次都不买,j从0开始,而不是从1开始
f[i & 1][j] = max(f[i & 1][j], g[i - 1 & 1][j - 1] + prices[i - 1]);
}
int ans = 0;
for (int i = 0; i <= k; i++)
ans = max(ans, f[n & 1][i]);
return ans;
}
};
优化一维状态代码:
// 将vector换成了数组,大概会快50%。
// 类似于背包问题优化空间,将原本的滚动二维数组,直接换成一维数组。
int f[10001], g[10001];
class Solution {
public:
int maxProfit(int k, vector<int>& prices) {
int INF = 1e8;
int n = prices.size();
if (k > n / 2) {
int res = 0;
for (int i = 1; i < n; i ++ )
if (prices[i] > prices[i - 1])
res += prices[i] - prices[i - 1];
return res;
}
memset(f, -0x3f, sizeof f);
memset(g, -0x3f, sizeof g);
f[0] = 0;
int res = 0;
for (int i = 1; i <= n; i ++ )
for (int j = k; j >= 0; j -- ) {
g[j] = max(g[j], f[j] - prices[i - 1]);
if (j) f[j] = max(f[j], g[j - 1] + prices[i - 1]);
}
for (int i = 1; i <= k; i ++ ) res = max(res, f[i]);
return res;
}
};
方法二:线性dp
大佬里面讲解了线性 dp
的做法,集合划分的相当清楚。且详细讲解了滚动数组的应用,及为什么能进行应用。真的强,建议好好学习一下~