我在leetcode用动态规划炒股

事情是这样的，突然兴起的我在letcode刷题

• 121. 买卖股票的最佳时机
• 122. 买卖股票的最佳时机 II
• 123. 买卖股票的最佳时机 III

以上三题。

1. 121. 买卖股票的最佳时机

1.1. 暴力遍历，两次遍历

1.1.1. 算法代码

public class Solution {public int MaxProfit(int[] prices) {int profitValue=0;for(int i=0;i<prices.Length;i++){for(int j=i+1;j<prices.Length;j++){if(prices[j]>prices[i]){if(prices[j]-prices[i]>profitValue){profitValue=prices[j]-prices[i];}}}}return profitValue;}
}

上述代码的逻辑为两次遍历，后一个值比前一个值大，并使用哨兵变量profitValue记录最大差值。

1.1.2. 算法复杂度

• 时间复杂度：$O(n^2)=\frac{n\ast (n-1)}{2}$
• 空间复杂度：$O(1)$,因为只有哨兵变量profitValue

1.1.3. 算法问题

前面我们讲到，这个时间复杂度是$O(n^2)$,是一个指数函数。

那么在数据非常大的时候，其根据时间复杂度可以知道，其复杂度非常的高，如leetcode的超时案例

[886,729,539,474,5,653,588,198,313,111,38,808,848,364,819,747,520,568,583,253,605,442,779,903,217,284,927,33,859,75,418,612,174,316,167,40,945,740,174,279,985,133,38,919,528,844,101,291,673,561,.......
中间有3万个数值
.......561,644,484,868,53,936,186,35,219,84,455,971,922,862,434,553,948,857,491,622,162,934,66,486,569,690,596,506,452,635,690]

其时间复杂度是：$30000\ast 29999/2=449985000$,其计算数值大的可怕。

1.2. 一次遍历

1.2.1. 算法代码

public class Solution {public int MaxProfit(int[] prices) {int minprice = int.MaxValue;int maxprofit = 0;for (int i = 0; i < prices.Length; i++) {if (prices[i] < minprice) {minprice = prices[i];} else if (prices[i] - minprice > maxprofit) {maxprofit = prices[i] - minprice;}}return maxprofit;}
}

其算法，基本思路是：在最低点购入，在最高点卖出,由于for循环是从0开始的，所以其每一次minprice是当前时点前最低点购入值，故此算法可靠

1.2.2. 算法复杂度

• 时间复杂度：$O(n)$
• 空间复杂度：$O(1)=2$

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

第一题相较比较简单，而第二题中增加了一个限定：可以购买多次，只是手上最多只有一支股票

2.1. 贪心算法

2.1.1. 算法代码

public class Solution {public int MaxProfit(int[] prices) {int ans = 0;int n = prices.Length;for (int i = 1; i < n; ++i) {int diffPrice=prices[i] - prices[i - 1];if(diffPrice>0){ans += diffPrice;}}return ans;}
}

2.1.2. 算法思路与步骤

只要后一天的价格比今天高，那么我今天就买，后一天就卖。

2.1.3. 算法复杂度

• 时间复杂度：$O(n)$
• 空间复杂度：$O(1)=2$

2.2. 动态规划算法

2.2.1. 算法代码

public class Solution {public int MaxProfit(int[] prices) {if (prices.Length < 2) {return 0;}int[] OwnStocks=new int[prices.Length];int[] NoStocks=new int[prices.Length];OwnStocks[0]=-prices[0];NoStocks[0]=0;for(int i=1;i<prices.Length;i++){OwnStocks[i]=Math.Max(OwnStocks[i-1],NoStocks[i-1]-prices[i]);NoStocks[i]=Math.Max(NoStocks[i-1],OwnStocks[i-1]+prices[i]);}return NoStocks[prices.Length-1];}
}

2.2.2. 算法思路与步骤

• 由于不可以同时存在多支股票，所以每天只有可能有两种状态有股票、没有股票
• 第一天存在股票=0-第一天股票价值；第一天不存在股票=0(没有购买或者当天售出)
• 后续每一天，当天有股票的最大利益=Math.Max(前一天有股票的值,前一天没有股票的值-当天股票值[购买股票])
• 后续每一天，当前没有股票的最大利益=Math.Max(前一天没有股票的值,前一天有股票的值+当天股票值[卖出股票]`)

图解如下：

2.2.3. 算法复杂度

• 时间复杂度：$O(n)$
• 空间复杂度：$O(n)=2n$

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

2.3.1. 动态规划算法

这一题就和第二题的动态规划类似，只是第二题是两个状态，而第三题是四个状态。

• 没有买入
• 第一次买入，没有卖出
• 第一次买出，没有卖入
• 第二次买入，没有卖出
• 第二次买出

由于没有买入全程是0所以不做考虑，列出了5种，但实际上只有4种状态。

2.3.2. 算法代码

public class Solution {public int MaxProfit(int[] prices) {if(prices.Length<2){return 0;}int oneBuy=-prices[0];int oneSale=0;int twoBuy=-prices[0];int twoSale=0;for(int i=1;i<prices.Length;i++){oneBuy=Math.Max(oneBuy,-prices[i]);oneSale=Math.Max(oneSale,oneBuy+prices[i]);twoBuy=Math.Max(twoBuy,oneSale-prices[i]);twoSale=Math.Max(twoSale,twoBuy+prices[i]);}return twoSale;}
}

2.3.3. 算法复杂度

• 时间复杂度：$O(n)$
• 空间复杂度：$O(1)=4$