【算法挨揍日记】day24——309. 买卖股票的最佳时机含冷冻期、714. 买卖股票的最佳时机含手续费

╰半夏微凉° 2024-02-19 08:32 8阅读 0赞

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

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

### 题目描述： ###

给定一个整数数组`prices`，其中第 `prices[i]` 表示第 `i` 天的股票价格 。

设计一个算法计算出最大利润。在满足以下约束条件下，你可以尽可能地完成更多的交易（多次买卖一支股票）:

*  卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。

**注意：**你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

![114253f08c63461eb0a676010add5edd.png][]

### 解题思路: ###

> 算法思路： 
> 
> 1.  状态表⽰： 
> 
> 对于线性  dp  ，我们可以⽤「经验 + 题⽬要求」来定义状态表⽰： 
> 
> i.  以某个位置为结尾，巴拉巴拉； 
> 
> ii.  以某个位置为起点，巴拉巴拉。 
> 
> 这⾥我们选择⽐较常⽤的⽅式，以某个位置为结尾，结合题⽬要求，定义⼀个状态表⽰： 
> 
> 由于有「买⼊」「可交易」「冷冻期」三个状态，因此我们可以选择⽤三个数组，其中： 
> 
> ▪  dp\[i\]\[0\]  表⽰：第  i  天结束后，处于「买⼊」状态，此时的最⼤利润； 
> 
> ▪  dp\[i\]\[1\]  表⽰：第  i  天结束后，处于「可交易」状态，此时的最⼤利润； 
> 
> ▪  dp\[i\]\[2\]  表⽰：第  i  天结束后，处于「冷冻期」状态，此时的最⼤利润。 
> 
> 2.  状态转移⽅程： 
> 
> 我们要谨记规则： 
> 
> i.  处于「买⼊」状态的时候，我们现在有股票，此时不能买股票，只能继续持有股票，或者卖 
> 
> 出股票； 
> 
> ii.  处于「卖出」状态的时候： 
> 
> •  如果「在冷冻期」，不能买⼊； 
> 
> •  如果「不在冷冻期」，才能买⼊。 
> 
> ◦  对于  dp\[i\]\[0\]  ，我们有「两种情况」能到达这个状态： 
> 
> i.  在  i - 1  天持有股票，此时最⼤收益应该和  i - 1  天的保持⼀致：  dp\[i - 1\] \[0\] ； 
> 
> ii.  在 i 天买⼊股票，那我们应该选择 i - 1  天不在冷冻期的时候买⼊，由于买⼊需要花 钱，所以此时最⼤收益为： dp\[i - 1\]\[1\] - prices\[i\] 两种情况应取最⼤值，因此： dp\[i\]\[0\] = max(dp\[i - 1\]\[0\], dp\[i - 1\]\[1\] - prices\[i\]) 。 
> 
> ◦  对于  dp\[i\]\[1\]  ，我们有「两种情况」能到达这个状态： 
> 
> i.  在  i - 1  天的时候，已经处于冷冻期，然后啥也不⼲到第  i  天，此时对应的状态为： 
> 
> dp\[i - 1\]\[2\]  ； 
> 
> ii.  在  i - 1  天的时候，⼿上没有股票，也不在冷冻期，但是依旧啥也不⼲到第  i  天，此时 
> 
> 对应的状态为  dp\[i - 1\]\[1\]  ； 
> 
> 两种情况应取最⼤值，因此：  dp\[i\]\[1\] = max(dp\[i - 1\]\[1\], dp\[i - 1\]\[2\])  。 
> 
> ◦  对于  dp\[1\]\[i\]  ，我们只有「⼀种情况」能到达这个状态： 
> 
> i.  在  i - 1  天的时候，卖出股票。 
> 
> 因此对应的状态转移为：  dp\[i\]\[2\] = dp\[i - 1\]\[0\] + prices\[i\]  。 
> 
> 3.  初始化： 
> 
> 三种状态都会⽤到前⼀个位置的值，因此需要初始化每⼀⾏的第⼀个位置： 
> 
> dp\[0\]\[0\]  ：此时要想处于「买⼊」状态，必须把第⼀天的股票买了，因此  dp\[0\]\[0\] = - prices\[0\] ； 
> 
> dp\[0\]\[1\]  ：啥也不⽤⼲即可，因此  dp\[0\]\[1\] = 0  ； 
> 
> dp\[0\]\[2\]  ：⼿上没有股票，买⼀下卖⼀下就处于冷冻期，此时收益为  0  ，因此  dp\[0\]\[2\] = 0 。 
> 
> 4.  填表顺序： 
> 
> 根据「状态表⽰」，我们要三个表⼀起填，每⼀个表「从左往右」。 
> 
> 5.  返回值： 
> 
> 应该返回「卖出状态」下的最⼤值，因此应该返回  max(dp\[n - 1\]\[1\], dp\[n - 1\] \[2\]) 。

### 解题代码： ###

class Solution {
    public:
        int maxProfit(vector<int>& prices) {
            int n=prices.size();
            vector<vector<int>>dp(n,vector(3,0));
            dp[0][0]=-prices[0];
            for(int i=1;i<n;i++)
            {
                dp[i][0]=max(dp[i-1][0],dp[i-1][1]-prices[i]);
                dp[i][1]=max(dp[i-1][1],dp[i-1][2]);
                dp[i][2]=dp[i-1][0]+prices[i];
            }
            return max(dp[n-1][1],dp[n-1][2]);
        }
    };

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

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

### 题目描述： ###

给定一个整数数组 `prices`，其中 `prices[i]`表示第 `i` 天的股票价格 ；整数 `fee` 代表了交易股票的手续费用。

你可以无限次地完成交易，但是你每笔交易都需要付手续费。如果你已经购买了一个股票，在卖出它之前你就不能再继续购买股票了。

返回获得利润的最大值。

**注意：**这里的一笔交易指买入持有并卖出股票的整个过程，每笔交易你只需要为支付一次手续费。

### 解题思路： ###

> 状态表示：
> 
> dp\[i\]\[0\]表示第i天后，处于买入状态的最大利润
> 
> dp\[i\]\[0\]表示第i天后，处于可交易状态的最大利润
> 
> 状态转移方程：
> 
> 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\]);
> 
> 初始化：
> 
> dp\[0\]\[0\]=-prices\[0\]-fee;
> 
> 填表顺序：左到右
> 
> 返回值dp\[n-1\]\[1\]

### 解题代码： ###

class Solution {
    public:
        int maxProfit(vector<int>& prices, int fee) {
            int n=prices.size();
            vector<vector<int>>dp(n,vector<int>(2,0));
            dp[0][0]=-prices[0]-fee;
            for(int i=1;i<n;i++)
            {
                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]);
            }
            return dp[n-1][1];
        }
    };

[309.]: https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-with-cooldown/
[114253f08c63461eb0a676010add5edd.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/19/7518f46c6d8a44ea9b8c8a415175a2ed.png
[714.]: https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-with-transaction-fee/