欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

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

程序员文章站 2022-07-07 15:26:29
...

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 k\ge \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 的做法,集合划分的相当清楚。且详细讲解了滚动数组的应用,及为什么能进行应用。真的强,建议好好学习一下~