广州网站建设公司万齐网络科技,手工外包网,网页设计师初学者工资,网站建设和风险分析309. 买卖股票的最佳时机含冷冻期 - 力扣#xff08;LeetCode#xff09; 动态规划解题思路#xff1a;
1、暴力递归#xff08;难点如何定义递归函数#xff09;
2、记忆化搜索-傻缓存法#xff08;根据暴力递归可变参数确定缓存数组维度#xff09;
3、严格表结构依…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位置只依赖于index1位置的元素所以填数组的顺序为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位置只依赖于index1位置的元素也就是说index行的数据只依赖index1行的数据所以可以只用一个一维数组循环更新即可。 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 f0;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 buy0,sell0;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 times0;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];} 该题就没啥可空间优化所以到这就结束了。我觉得这个代码是最好理解的。
