Leetcode用交易费买卖股票的最佳时机，如何思考

Question

我了解用交易费购买和出售股票的最佳时间的解决方案，以及与股票出售相关的其他5个问题。我只想深入了解如何在问题中提出这种递归关系。

我读过https://leetcode.com/problems/best-time-to-buy-and-sell-stock-with-transaction-fee/discuss/108870/most-consistent-ways-of-dealing-with-the-series-of-stock-problems我完全理解。

但是，我在解决一些类似的问题时遇到了一些小问题，例如，如果一个人可以购买股票而不出售之前先购买的股票。

那么，提出正确的递归关系的一般方法是什么？

我真的很困惑非常感谢

Answer 1

 class Solution {
   public int maxProfit(int[] prices, int fee) {
    if (prices == null || prices.length <= 1) {
        return 0;
    } 
    long profit = 0, minPrice = Integer.MIN_VALUE;
    //Integer.MIN_VALUE = - 2147483648

  for (int price : prices) {
    long profit_old = profit;
    profit = Math.max(profit, minPrice + price - fee);
    minPrice = Math.max(minPrice, profit_old - price);  
   }  

  return (int)profit;

  }
}

你的输入[1,3,2,8,4,9]2

看看利润如何

利润0. minPrice-1

利润0分钟价格-1

利润0分钟价格-1

利润5分钟价格-1

利润5分钟价格1

利润8分钟价格1

所以最终最大利润是8。

Answer 2

假设给定的数组是：

[7, 1, 5, 3, 6, 4]

如果我们将给定数组的数字绘制在一张图上，我们会得到：

利润图

感兴趣的点是给定图表中的波峰和波谷。我们需要在最小的山谷之后找到最大的山峰。我们可以维护两个变量——minprice和maxprofit，分别对应到目前为止获得的最小谷值和最大利润（售价和minprice之间的最大差值）。

class Solution {
  public int maxProfit(int[] prices) {
     int max = 0;
     int min = Integer.MAX_VALUE;

     for(int i = 0 ; i < prices.length ; i++) {
        if(prices[i] < min) {
            min = prices[i];
        }else {
            max = Math.max(max, prices[i] - min);
        }
     }

     return max; 
  }
}

Answer 3

这个问题有两种情况

案例1：当我在第一天有一只股票，用dp[I][1]表示时，选择最大值低于2点

 case 1a : I bought it today.
dp[i][1] = dp[i-1][0]-prices[i]-fee

 case 1b : I am carrying a pre-bought stock
dp[i][1] = dp[i-1][1]

案例2：当我在第一天没有股票时，表示为dp[I][0]

case 2a : I sold it today
dp[i][0] = dp[i-1][1]+prices[i]

 case 2b : I sold the stock at some other previous day, doing nothing
dp[i][0] = dp[i-1][0]

下面是c语言中的代码#

public int MaxProfit(int[] prices, int fee) {
        int n = prices.Length;
        if(n<=1)
            return 0;
        int[,] dp=new int[n,2];
        dp[0,0] = 0;
        dp[0,1] = -prices[0]-fee;
        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,0];
    }