leetcode:123. 买卖股票的最佳时机 III(暴力+递归)

分手后的思念是犯贱 2021-09-28 14:02 294阅读 0赞

给定一个数组，它的第* i* 个元素是一支给定的股票在第 *i *天的价格。

设计一个算法来计算你所能获取的最大利润。你最多可以完成 *两笔 *交易。

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

**示例 1:**

输入: [3,3,5,0,0,3,1,4]
    输出: 6
    解释: 在第 4 天（股票价格 = 0）的时候买入，在第 6 天（股票价格 = 3）的时候卖出，这笔交易所能获得利润 = 3-0 = 3 。
         随后，在第 7 天（股票价格 = 1）的时候买入，在第 8 天 （股票价格 = 4）的时候卖出，这笔交易所能获得利润 = 4-1 = 3 。

**示例 2:**

输入: [1,2,3,4,5]
    输出: 4
    解释: 在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。   
         注意你不能在第 1 天和第 2 天接连购买股票，之后再将它们卖出。   
         因为这样属于同时参与了多笔交易，你必须在再次购买前出售掉之前的股票。

**示例 3:**

输入: [7,6,4,3,1] 
    输出: 0 
    解释: 在这个情况下, 没有交易完成, 所以最大利润为 0。

public int maxProfit(int[] prices) {
            if (prices.length == 0) return 0;
            return dfs(prices, 0, 0, false);
        }
        /*
            手中是否有股票 h
            第几天 i
            count 最多能交易两次 记录买入的次数 如果买入两次并且手中已经没有股票了意味着交易两次了
            选择 买 卖
         */
    
        public int dfs(int[] prices, int i, int count, boolean h) {
            //跳出递归的条件 当天数i大于prices的天数时，当已经买了两次了并且也全部抛出了
            if (i > prices.length || (count >= 2 && !h)) {
                return 0;
            }
            /*
            接下来的情况无非就是 两大种 手中是否有股票 如果有的话我 卖出还是不卖 ，如果没有的话我是买入还是不买
             */
            if (h) {
                //手中有股票卖还是不卖
                return Math.max(prices[i] + dfs(prices, i + 1, count, false), dfs(prices, i + 1, count, true));
            } else {
                //手中没有股票我选择买还是不买
                return Math.max(dfs(prices, i + 1, count + 1, true) - prices[i], dfs(prices, i + 1, count, false));
            }
    
        }

动态规划：

public int maxProfitDP(int[] prices) {
            if (prices.length == 0) return 0;
            int m = prices.length;
            int[][][] res = new int[m + 1][3][2];
            for (int i = m - 1; i >= 0; i--) {
                for (int j = 2; j >= 0; j--) {
                    for (int k = 1; k >= 0; k--) {
                        if (j == 2 && k == 0) continue;
                        if (k > 0) {
                            //我手中有股票是卖出还是不卖
                            res[i][j][k] = Math.max(res[i + 1][j][0] + prices[i], res[i + 1][j][1]);
                        } else {
                            //我手中没股票是买入还是不买
                            res[i][j][k] = Math.max(res[i + 1][j + 1][1] - prices[i], res[i + 1][j][0]);
                        }
                    }
                }
            }
            return res[0][0][0];
        }