【leetcode买卖股票系列问题】多次买卖/手续费/冻结期

一、目录

一、目录

二、股票系列问题

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

1.1.题目

1.2.思路

1.3.代码实现（1种） 

2.买卖股票的最佳时机II（122题）

2.1.题目

 2.2.思路

2.3.代码实现（3种）

3.买卖股票的最佳时机III（123题）

3.1.题目

3.2.思路

3.3.代码实现（2种） 

4.买卖股票的最佳时机IV（188题）

4.1.题目

4.2.思路

 4.3.代码实现（1种）

5.买卖股票的最佳时机含冷冻期（309题）

5.1.题目

5.2.思路

5.3.代码实现（2种）

6.买卖股票的最佳时机含手续费（714题）

6.1.题目

6.2.思路

6.3.代码实现（2种） 

7.股票的最大利润（剑指Offer63题）

三、总结

二、股票系列问题

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

1.1.题目

1.2.思路

dp：根据题目要求，我们只有一次买卖股票的机会，设dp[i]表示第i天结束后的最大利润，要想使某日的利润最大，那就需要找出该日之前的价格最小的一天，然后相减，也就是dp[i]=max(dp[i],prices[i]-prices[之前最小的])，这里可以直接省略dp数组，动态维护一个int值。 

1.3.代码实现（1种） 

    class Solution {
        /**
         * dp:dp[i]表示在第i天卖出时的最大利润，此题可以省去dp数组，只需要动态维护一个int值即可
         * 在某一天买入，然后在后边的某一天卖出，当这天卖出时，最大的利润就是当天的价钱-之前的最小价钱
         * 所以需要动态维护i-1天的最小价钱，然后计算第i天卖出的价钱，再去动态维护0~i天的最大利润
         */
        public int maxProfit(int[] prices) {
            int n = prices.length;
            int minPrice = prices[0]; //记录i-1天的最低价钱，初始化为第一天的price
            int maxProfit = 0; //记录最大利润，0表示未买入
            for (int i = 1; i < n; i++) {
                minPrice = Math.min(minPrice, prices[i - 1]);
                maxProfit = Math.max(maxProfit, prices[i] - minPrice);
            }
            return maxProfit;
        }
    }

2.买卖股票的最佳时机II（122题）

2.1.题目

 2.2.思路

与I相比，该题不限制我们买卖股票的次数。

1.贪心：把股票价格看成一个折线图，x轴是天数，y轴是价格，那么折线图上升的时期就是股票盈利的时期，既然不要求买卖次数，那么我们可以两天两天地去判断（因为买入卖出要分为两天），若当天的价格>前一天的价格，那么就把他们的差值累加，最后得到的就是所有上升时期所盈利的利润。

2.dp：设dp[i]为第i天结束后的最大收益，此时分为两种状态，手里有股票dp[i][0]和手里没股票dp[i][1]，推动态转移方程：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][0]+prices[i])，今天没股票，说明昨天也没有股票或者是昨天还有股票，今天卖掉了股票。

2.3.代码实现（3种）

2.3.1 贪心

    public int maxProfit1(int[] prices) {
            int ans = 0;
            for (int i = 1; i < prices.length; i++) {
                if (prices[i] - prices[i - 1] > 0) {
                    ans += prices[i] - prices[i - 1];
                }
            }
            return ans;
        }

 2.3.2 dp（无空间优化）

    public int maxProfit2(int[] prices) {
            int n = prices.length;
            int[][] dp = new int[n][2];
            dp[0][0] = -prices[0]; //第0天有股票说明今天买了，初始化-prices[0]，其他值默认为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][0] + prices[i], dp[i - 1][1]);
            }
            //最后一天手里还有股票无意义，直接返回dp[n-1][1]
            return dp[n - 1][1];
            //注意到第i天结束后的最大利润之和i-1有关，则可以优化空间复杂度
        }

2.3.3 dp（有空间优化）

        /**
         * 1.贪心：因为不限制买卖次数，只限制同一时间持有一支股票的话，那可以随时进行买卖
         * 只需要计算出所有上升的差值即可，即prices[i]-prices[i-1]
         * 2.dp：设dp[i]代表第i天结束的最大利润，此时有2种状态，手里有股票和没股票
         * 有股票dp[i][0]，没有股票是dp[i][1]，
         * dp[i][0]=max(dp[i-1][0],dp[i-1][1]-prices[i])，可以是上一天的股票，也可以是上一天没股票，今天才买
         * dp[i][1]=max(dp[i-1][0]+prices[i],dp[i-1][1])，今天没有股票，说明是昨天还有股票，今天卖了，或者是之前就卖了
         */
        public int maxProfit(int[] prices) {
            int n = prices.length;
            int hold = -prices[0]; //第0天有股票说明今天买了，初始化-prices[0]
            int no = 0; //记录当天结束后没有股票
            for (int i &