leetcode-买卖股票问题

309. 买卖股票的最佳时机含冷冻期 - 力扣（LeetCode）

        动态规划解题思路：

1、暴力递归（难点如何定义递归函数）

2、记忆化搜索-傻缓存法（根据暴力递归可变参数确定缓存数组维度）

3、严格表结构依赖的动态规划

4、进一步优化（斜率优化、空间优化），非必须

一、分析：假设[0,index-1]之前的最大利润已经知道，现在计算到了index位置的最大利润。根据题意，到index位置后可能有三种状态，买入、卖出、冷冻。所以递归函数如下。

    public int maxProfit(int[] prices) {return p(prices,0,0);}// 0-买入 1-卖出 2-冷冻// 递归函数表示 从index位置到prices.length-1位置的最大利润public int p(int[] prices, int index, int state) {if (index == prices.length) {return 0;}int res = 0;if (state == 0) {// 买入 当前indexint p1 = -prices[index] + p(prices, index + 1, 1);// 不买当前indexint p2 = p(prices, index + 1, 0);return Math.max(p1, p2);} else if (state == 1) {// 卖当前indexint p1 = prices[index] + p(prices, index + 1, 2);// 不卖当前indexint p2 = p(prices, index + 1, 1);return Math.max(p1, p2);} else {//冷冻return p(prices, index + 1, 0);}}

二、我们直接看表依赖，略过傻缓存法。根据暴力递归函数分析，有两个可变参数，所以申请一个二维数组即可，看递归的base case初始化dp数组；看依赖关系index位置只依赖于index+1位置的元素，所以填数组的顺序为index倒序。返回值看递归调用的参数值是什么，就返回dp数组哪个位置的值。

    public int maxProfit2(int[] prices) {int N = prices.length;int[][] dp = new int[N + 1][3];for (int index = N - 1; index >= 0; index--) {dp[index][2] = dp[index + 1][0];dp[index][1] = Math.max(prices[index] + dp[index + 1][2], dp[index + 1][1]);dp[index][0] = Math.max(-prices[index] + dp[index][1], dp[index + 1][0]);}return dp[0][0];}

三、我们分析知道index位置只依赖于index+1位置的元素，也就是说index行的数据只依赖index+1行的数据，所以可以只用一个一维数组，循环更新即可。

    public int maxProfit(int[] prices) {int N = prices.length;//空间优化int[] dp = new int[3];for (int index = N - 1; index >= 0; index--) {int temp = dp[0];dp[0] = Math.max(-prices[index] + dp[1], dp[0]);dp[1] = Math.max(prices[index] + dp[2], dp[1]);dp[2] = temp;}return dp[0];}

 714. 买卖股票的最佳时机含手续费 - 力扣（LeetCode）

        该题的解法和上题类似，只是多了手续费，少了冷冻期。

一、暴力递归

    int f=0;public int maxProfit1(int[] prices, int fee) {f = fee;return p(prices, 0, 0);}// 0-买入 1-卖出public int p(int[] prices, int index, int state) {if (index == prices.length) {return 0;}int res = 0;if (state == 0) {// 买入 当前indexint p1 = -prices[index] - f + p(prices, index + 1, 1);// 不买当前indexint p2 = p(prices, index + 1, 0);return Math.max(p1, p2);} else {// 可以卖int p1 = prices[index] + p(prices, index + 1, 0);int p2 = p(prices, index + 1, 1);return Math.max(p1, p2);}}

二、表结构动态规划

    public int maxProfit2(int[] prices, int fee) {int N = prices.length;int[][] dp = new int[N + 1][2];for (int index = N - 1; index >= 0; index--) {dp[index][1] = Math.max(prices[index] + dp[index + 1][0], dp[index + 1][1]);dp[index][0] = Math.max(-prices[index] - fee + dp[index][1], dp[index + 1][0]);}return dp[0][0];}

三、空间优化

    public int maxProfit4(int[] prices, int fee) {int N = prices.length;// 空间优化int buy=0,sell=0;for (int index = N - 1; index >= 0; index--) {int temp = buy;buy = Math.max(-prices[index] - fee + sell, buy);sell = Math.max(prices[index] + temp, sell);}return buy;}public int maxProfit3(int[] prices, int fee) {int N = prices.length;// 空间优化int[] dp = new int[2];for (int index = N - 1; index >= 0; index--) {int temp = dp[0];dp[0] = Math.max(-prices[index] - fee + dp[1], dp[0]);dp[1] = Math.max(prices[index] + temp, dp[1]);}return dp[0];}

123. 买卖股票的最佳时机 III - 力扣（LeetCode）

        该题的差异在于：没有冷冻期、没有手续费，但是限制了交易次数，也就是说我们的可变参数需要再加一个交易次数即可。

一、暴力递归

    public int maxProfit1(int[] prices) {return p(prices, 0, 0, 0);}public int p(int[] prices, int index, int state, int count) {if (index == prices.length) {return 0;}if (count == 2) {return 0;}int p1 = 0, p2 = 0;if (state == 0) {// buyp1 = -prices[index] + p(prices, index + 1, 1, count);p2 = p(prices, index + 1, 0, count);} else {// 卖出p1 = prices[index] + p(prices, index + 1, 0, count + 1);p2 = p(prices, index + 1, 1, count);}return Math.max(p1, p2);}

二、动态规划

    public int maxProfit2(int[] prices) {int N = prices.length;// state countint[][][] dp = new int[N + 1][2][3];for (int index = N - 1; index >= 0; index--) {for (int count = 1; count >= 0; count--) {dp[index][0][count] = Math.max(-prices[index] + dp[index + 1][1][count], dp[index + 1][0][count]);dp[index][1][count] = Math.max(prices[index] + (count + 1 == 2 ? 0 : dp[index + 1][0][count + 1]),dp[index + 1][1][count]);}}return dp[0][0][0];}

三、空间优化（从下至上逐步优化到最优的maxProfit5）

    public int maxProfit5(int[] prices) {int N = prices.length;// state countint buy1 = 0;int sell1 = 0;int buy2 = 0;int sell2 = 0;for (int index = N - 1; index >= 0; index--) {buy2 = Math.max(-prices[index] + sell2, buy2);sell2 = Math.max(prices[index], sell2);buy1 = Math.max(-prices[index] + sell1, buy1);sell1 = Math.max(prices[index] + buy2, sell1);}return buy1;}public int maxProfit4(int[] prices) {int N = prices.length;// state count dp[0][0] 买1 dp[0][1]买2 dp[1][0]卖1 dp[1][1] 卖2int[][] dp = new int[2][3];for (int index = N - 1; index >= 0; index--) {dp[0][1] = Math.max(-prices[index] + dp[1][1], dp[0][1]);dp[1][1] = Math.max(prices[index], dp[1][1]);dp[0][0] = Math.max(-prices[index] + dp[1][0], dp[0][0]);dp[1][0] = Math.max(prices[index] + dp[0][1], dp[1][0]);}return dp[0][0];}public int maxProfit3(int[] prices) {int N = prices.length;// state countint[][] dp = new int[2][3];for (int index = N - 1; index >= 0; index--) {for (int count = 1; count >= 0; count--) {dp[0][count] = Math.max(-prices[index] + dp[1][count], dp[0][count]);dp[1][count] = Math.max(prices[index] + (count + 1 == 2 ? 0 : dp[0][count + 1]), dp[1][count]);}}return dp[0][0];}

188. 买卖股票的最佳时机 IV - 力扣（LeetCode）

        该题解法和上题类似，只是交易次数为k。

一、暴力递归

    int times=0;public int maxProfit1(int k, int[] prices) {times = k;return p(prices, 0, 0, 0);}public int p(int[] prices, int index, int state, int count) {if (index == prices.length) {return 0;}if (count == times) {return 0;}int p1 = 0, p2 = 0;if (state == 0) {// buyp1 = -prices[index] + p(prices, index + 1, 1, count);p2 = p(prices, index + 1, 0, count);} else {// 卖出p1 = prices[index] + p(prices, index + 1, 0, count + 1);p2 = p(prices, index + 1, 1, count);}return Math.max(p1, p2);}

二、动态规划

    public int maxProfit(int k, int[] prices) {int N = prices.length;// state countint[][] dp = new int[2][k];for (int index = N - 1; index >= 0; index--) {for (int count = k - 1; count >= 0; count--) {dp[0][count] = Math.max(-prices[index] + dp[1][count], dp[0][count]);dp[1][count] = Math.max(prices[index] + (count + 1 == k ? 0 : dp[0][count + 1]), dp[1][count]);}}return dp[0][0];}

        该题就没啥可空间优化，所以到这就结束了。我觉得这个代码是最好理解的。