区块链技术博客
www.b2bchain.cn

[Hdp] lc188. 买卖股票的最佳时机 IV(状态机模型dp+线性dp+空间优化)

这篇文章主要介绍了[Hdp] lc188. 买卖股票的最佳时机 IV(状态机模型dp+线性dp+空间优化)的讲解,通过具体代码实例进行17726 讲解,并且分析了[Hdp] lc188. 买卖股票的最佳时机 IV(状态机模型dp+线性dp+空间优化)的详细步骤与相关技巧,需要的朋友可以参考下https://www.b2bchain.cn/?p=17726

本文实例讲述了2、树莓派设置连接WiFi,开启VNC等等的讲解。分享给大家供大家参考文章查询地址https://www.b2bchain.cn/7039.html。具体如下:

文章目录

    • 1. 题目来源
    • 2. 题目说明
    • 3. 题目解析
      • 方法一:状态机模型dp
      • 方法二:线性dp

1. 题目来源

链接:lc188. 买卖股票的最佳时机 IV

2. 题目说明

[Hdp] lc188. 买卖股票的最佳时机 IV(状态机模型dp+线性dp+空间优化)

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 kge frac n 2 k2n 那么这就相当于交易无限次,那么就可以采用 [Edp] lc122. 买卖股票的最佳时机 II(dp+思维) 来进行求解了,求每个正区间累加即可

  • 考虑一次交易所经历的阶段

    • 第一阶段:买入股票还没卖出
    • 第二阶段:卖出股票
  • 状态机定义: 用 0 表示交易完,所有手里没股票的状态,1 表示所有没交易完,手里有股票还没卖的状态

  • 状态机起点: 第一天手里没有股票,走向状态 0

  • 状态 0 分析: 如果我们不买股票,那么手里依旧没有股票,则状态转移从状态 0 转移到状态 0,且当前总钱数未发生改变,+0。同理,也可以买入股票,状态转移从状态 0 转移到状态 1,则表示我们买入股票,则当前总钱数需要 -wi

  • 状态 1 分析: 如果我们不买股票,那么手里依旧没有股票,则状态转移从状态 1 转移到状态 1,且当前总钱数未发生改变,+0。同理,也可以卖出股票,状态转移从状态 1 转移到状态 0,则表示我们卖出股票,则当前总钱数需要 +wi

  • 状态机终点: 状态机终点一定在手里没有股票的情况

  • 最多交易 k 次: 等价于在两个状态之间最多只能转 k

  • [Hdp] lc188. 买卖股票的最佳时机 IV(状态机模型dp+线性dp+空间优化)

  • 问题转化为从起点出发最多转 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

ORZ 参考大佬题解

大佬里面讲解了线性 dp 的做法,集合划分的相当清楚。且详细讲解了滚动数组的应用,及为什么能进行应用。真的强,建议好好学习一下~

本文转自互联网,侵权联系删除[Hdp] lc188. 买卖股票的最佳时机 IV(状态机模型dp+线性dp+空间优化)

赞(0) 打赏
部分文章转自网络,侵权联系删除b2bchain区块链学习技术社区 » [Hdp] lc188. 买卖股票的最佳时机 IV(状态机模型dp+线性dp+空间优化)
分享到: 更多 (0)

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

b2b链

联系我们联系我们