AlgoPressAppearance
0714-买卖股票的最佳时机含手续费
https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-with-transaction-fee
给定一个整数数组 prices，其中第 i 个元素代表了第 i 天的股票价格 ；整数 fee 代表了交易股票的手续费用。 你可以无限次地完成交易，但是你每笔交易都需要付手续费。如果你已经购买了一个股票，在卖出它之前你就不能再继续购买股票了。 返回获得利润的最大值。
注意：这里的一笔交易指买入持有并卖出股票的整个过程，每笔交易你只需要为支付一次手续费。
示例 1：
输入：prices = [1, 3, 2, 8, 4, 9], fee = 2
输出：8
解释：能够达到的最大利润:
在此处买入 prices[0] = 1
在此处卖出 prices[3] = 8
在此处买入 prices[4] = 4
在此处卖出 prices[5] = 9
总利润: ((8 - 1) - 2) + ((9 - 4) - 2) = 8
示例 2：
输入：prices = [1,3,7,5,10,3], fee = 3
输出：6
提示：
1 <= prices.length <= 5 * 10^4
1 <= prices[i] < 5 * 10^4
0 <= fee < 5 * 10^4
思路分析
- 取得最低价格 minValue
- 遍历到当前i，看prices[i] - minValue - fee 是否大于0，是就购买
- 如果购买之后，就更新 minValue 为当前价格 ?? 这里有问题，如果后续还买卖，且价格比当前高，那么这个fee是可以省下来的 所以我们需要记录，购买之后的 minValue 和不购卖的 minValue , 就是突然很难想明白
====
上述思路又回到传统思路，用动态规划的方法思考。 每天的状态有两种 持有股票，或者不持有股票， 记录两种状态的最大收益 持有股票： 有可能是前一天没有持有股票，今天买入了. 也可能就是前一天持有的 两者取 max 未持有股票： 有可能是前一天持有了，今天卖掉。 或者前一天没有持有，今天继续不持有，两者取 max
注意第一天，如果持有股票的话，收益是付的，因为还没有卖掉，就欠 prices[0] 的钱，后面同样如果持有，收益就减去当天的 prices[i] 最后一次返回的时候，就选择未持有股票的收益。
理解之后，写出以下代码
参考代码
csharp
public class Solution {
public int MaxProfit(int[] prices, int fee) {
if(prices.Length == 0){
return 0;
}
int noStock = 0; //手里没有股票 的最大收益
int hasStock = -prices[0]; //手里有股票 的最大收益
for(int i=1; i<prices.Length; i++){
int newNoStock = Math.Max(noStock, hasStock + prices[i] - fee ); //昨天就没有股票，或者昨天有股票今天卖掉了
int newHasStock = Math.Max(hasStock,noStock-prices[i]); //昨天就有股票，或者昨天没有股票，今天买入(但需要减去prices[i]的收益)
noStock = newNoStock;
hasStock = newHasStock;
}
return noStock;
}
}
参考代码 : 复习 2022-04-02
csharp
public class Solution{
public int MaxProfit(int[] prices, int fee){
if(prices.Length == 0){
return 0;
}
//动态规划 dp[i,0] 表示不持有股票的最大收益， dp[i,1] 表示持有股票的最大收益
int[,] dp = new int[prices.Length,2];
//初始化
dp[0,0] = 0;
dp[0,1] = -prices[0]; //持有股票，此时利润是 -prices[0];
for(int i = 1; i<prices.Length; i++){
//不持有股票(昨天就不持有，或者昨天持有今天卖掉了)
dp[i,0] = Math.Max(dp[i-1,0], dp[i-1,1] + prices[i] - fee );
//持有股票(昨天就持有股票，或者昨天不持有，今天持有了)
dp[i,1] = Math.Max(dp[i-1,1], dp[i-1,0] - prices[i]);
}
return dp[prices.Length-1,0];
}
}
参考代码: 复习，滚动数组
csharp
public class Solution {
public int MaxProfit(int[] prices, int fee) {
if(prices.Length == 0){
return 0;
}
int noStock = 0; //没有股票的收益
int hasStock = -prices[0]; //第一天持有股票的收益
for(int i = 1; i < prices.Length; i++){
// 昨天就不持有，或者昨天持有，今天卖掉
int newNoStock = Math.Max(noStock,hasStock + prices[i] - fee);
// 昨天不持有，今天持有
int newHasStock = Math.Max(hasStock, noStock - prices[i]);
noStock = newNoStock;
hasStock = newHasStock;
}
return noStock;
}
}
复习动归
csharp
public class Solution {
public int MaxProfit(int[] prices, int fee) {
//动态规划，定义 dp 数组 dp[i,2] dp[i,0] 表示第i天不持有股票的收益，dp[i,1] 表示第i天持有股票的收益
int[,] dp = new int[prices.Length,2];
dp[0,0] = 0;
dp[0,1] = -prices[0]; //注意持有股票的收益是负的，只有卖出时才能兑现。
for(int i=1; i<prices.Length; i++){
//不持有股票
dp[i,0 ] = Math.Max(dp[i-1,0], prices[i] + dp[i-1,1] - fee);
//持有股票
dp[i,1] = Math.Max(dp[i-1,0] - prices[i], dp[i-1,1]);
}
return dp[prices.Length-1,0];
}
}
复习：20220620
csharp
public class Solution {
public int MaxProfit(int[] prices, int fee) {
//动态规划
//dp[i,0] 表示第i天不持有股票的最大利润
//dp[i,1] 表示第i天持有股票的最大利润
int n = prices.Length;
int[,] dp = new int[n,2];
//初始化
dp[0,0] = 0;
dp[0,1] = -prices[0]; //持有股票利润是负数
for(int i=1; i<prices.Length; i++){
dp[i,0] = Math.Max(dp[i-1,0], dp[i-1,1] + prices[i] - fee); // 前一天不持有，或者前一天持有，当天卖掉。
dp[i,1] = Math.Max(dp[i-1,1], dp[i-1,0] - prices[i]); //前一天就持有，或者前一天不持有，今天买入
}
return dp[n-1,0];
}
}
复习：20220701
csharp
public class Solution {
public int MaxProfit(int[] prices, int fee) {
int n = prices.Length;
int[,] dp = new int[n,2];
dp[0,0] = -prices[0]; //持有股票的利润
dp[0,1] = 0; //售出股票的利润
for(int i=1; i<n; i++){
dp[i,0] = Math.Max(dp[i-1,0], dp[i-1,1] - prices[i]);
dp[i,1] = Math.Max(dp[i-1,1], dp[i-1,0] + prices[i] - fee);
}
return dp[n-1,1];
}
}