股票购买问题

股票购买问题

121.买卖股票的最佳时机

122. 买卖股票的最佳时机 II

123. 买卖股票的最佳时机 III

188. 买卖股票的最佳时机 IV

309. 最佳买卖股票时机含冷冻期

714. 买卖股票的最佳时机含手续费

​ 从讨论区看到了一篇很好的题解,把这一类问题全部汇总了,自己尝试写一篇加深一下记忆。贴上原文链接

​ 以第四题为例

0Dd1sS.png

​ 第一题是只能进行一次买卖,所以 $k = 1$,第二题,可以进行多次交易即 $k = INF$,第三题,只能进行两次交易,即 $k = 2$,第四题如让,$k$ 可以是任意值,第五题与第六题都是 $k = INF$,只是多了一些其他的状态。

​ 依照我超哥所说,这不显然 $dp[i][j][k]$ 么?所以开始定义状态 $dp$ 方程,定义 $i$ 代表在第 $i$ 天, $j$ 代表进行了 $j$ 次交易,$k$ 代表当前情况下手中是否有股票,$k$ 代表手中是否有股票,所以取值只有 $0$ 或者 $1$,$0$ 代表没有,$1$ 代表有。所以 $dp[i][j][0]$,代表在第 $i$ 天,进行了 $j$ 次交易,手中没有股票的情况下所获得的最大利润。$dp[i][j][1]$ 同理。所以最后我们返回 $dp[n][k][0]$,即第 $n$ 天,交易了 $k$ 次,手中没有股票的累计最大利润。为什么不返回$dp[n][k][1]$,那股票买了砸手里肯定比卖出去赚的少啊,所以最后手里肯定是不要剩股票最优。理解了上述状态开始定义状态转移方程。

情况定义如下:

  • 当 $j = 0$ 时,代表当天手中没有股票,那么它可以从如下几种状态转移过来
    • 前一天手中没有股票,直接转移
    • 前一天手中有股票,今天卖了
  • 当 $j = 1$ 时,代表当天手中有股票,那么它可以从如下几个状态转移过来
    • 前一天手中有股票,直接转移
    • 前一天手中没有股票,今天购买

​ 由于交易代表一次购买,一次出售,所以定义当购买时我们会花费一次交易,当出售时不会消耗交易次数。购买是将自己的钱给别人,出售则相反,所以定义购买时减去当前股票的价格,出售时增加当前股票的价格。

所以状态转移方程如下:
$$
dp[i][j][0] = max(dp[i-1][j][0], dp[i-1][j][1] + price[i])
$$

$$
dp[i][j][1] = max(dp[i-1][j][1], dp[i-1][j-1][0] - prices[i])
$$

理解到这里最难的部分已经解决了,开始初始化一些状态,如下

为了方便计算,防止数组越界,让 $i$ 从 $1$,开始,同理交易次数 $j$ 也是从 $1$ 开始。

当 $i = 0$ 时做任何操作,即还没开始购买,如果此时手中有股票,那么一定是非法的即手中累计 $-INF$,有如下初始化

for(int i = 0;i <= n;i++)
    dp[0][i][1] = INT_MIN;//在第 0 天 无论进行多少次购买,手中都不可能有股票

当 $j = 0$ 时,无论在那一天手中有股票也同样非法,有如下初始化

for(int i = 0;i <= n;i++)
    dp[i][0][1] = INT_MIN;

其余状况都是 $0$.

总结如下,按照题意进行改写即可

for(int i = 0;i <= n;i++)
	dp[i][0][1] = INT_MIN;
for(int i = 0;i <= mk;i++)
	dp[0][i][1] = INT_MIN;
for(int i = 1;i <= n;i++) { 
	for(int j = 1;j <= mk;k++) {
		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][mk][0];

当 $k = INF$ 时,第二维可以取消,因为当 $k$ 无限大时 $k \approx k - 1$。

309. 最佳买卖股票时机含冷冻期

由于购买需要冷冻一天,那么当需要购买股票的时候应该从 $i - 2$ 那天转移过来,而非 $i - 1$,注意数组不要越界。


class Solution {
public:
    int maxProfit(vector<int>& prices) {
        if(prices.size() == 0)
            return 0;
        int n = prices.size();
        vector<vector<int>> dp(n + 1, vector<int>(2, 0));
        dp[0][0] = 0;
        dp[0][1] = INT_MIN;
        for(int i = 1;i <= n;i++) {
            dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i-1]);
            if(i >= 2)	//特判一下,不要越界
                dp[i][1] = max(dp[i-1][1], dp[i-2][0] - prices[i-1]);
            else 
                dp[i][1] = max(dp[i-1][1], -prices[i-1]);
        }
        return dp[n][0];
    }
};

714. 买卖股票的最佳时机含手续费

只需要在购买的时候多花点钱就行了


class Solution {
public:
    int maxProfit(vector<int>& prices, int fee) {
        if(prices.size() == 0)
            return 0;
        int n = prices.size();
        vector<vector<int>> dp(n + 1, vector<int>(2, 0));
        dp[0][0] = 0;
        dp[0][1] = INT_MIN;
        for(int i = 1;i <= n;i++) {
            dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i-1]);
            dp[i][1] = max(dp[i-1][1], dp[i-1][0] - prices[i-1] - fee);//减去手续费
        }
        return dp[n][0];
    }
};

188. 买卖股票的最佳时机 IV

这题有一个需要注意的点,就是当 $k$ 很大时,因为要开三维$dp$,会炸空间,所以进行一些特判。由于交易是一天买,一天卖,一次交易至少需要两天所以当 $k \geq n/2$ 可以认为 $k \approx INF$,进而转化为第二类问题求解。

class Solution {
public:
    int maxProfit(int k, vector<int>& prices) {
        if(prices.size() == 0)
            return 0;
        int n = prices.size();
        const int mk = k;
        if(k >= n / 2) { //转为第二类问题
            return maxProfitK_INF(prices);
        }
        vector<vector<vector<int>>> dp(n + 1, vector<vector<int>>(mk + 1, vector<int>(2, 0)));
        for(int i = 0;i <= n;i++)
            dp[i][0][1] = INT_MIN;
        for(int i = 0;i <= mk;i++)
            dp[0][i][1] = INT_MIN;
        for(int i = 1;i <= n;i++) { 
            for(int k = 1;k <= mk;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][mk][0];
    }

    int maxProfitK_INF(vector<int>& prices) {
        int ans = 0;
        for(int i = 1;i < prices.size();i++) {
            ans +=  max(0, prices[i] - prices[i-1]);
        }
        return ans;
    }
};