网站建设信息科技公司,石林县工程建设个体交易网站,太原seo招聘,做幼儿手工网站目录#xff1a;一.题目知识点#xff1a;动态规划二.动态规划数组思路确定1.dp数组以及下标的含义2.确定递推公式3.dp数组如何初始化4.确定遍历顺序5.举例推导dp数组一.题目知识点#xff1a;动态规划动态规划算法的基本思想是#xff1a;将待求解的问题分解成若干个相互联…目录一.题目知识点动态规划二.动态规划数组思路确定1.dp数组以及下标的含义2.确定递推公式3.dp数组如何初始化4.确定遍历顺序5.举例推导dp数组一.题目知识点动态规划动态规划算法的基本思想是将待求解的问题分解成若干个相互联系的子问题先求解子问题然后从这些子问题的解得到原问题的解对于重复出现的子问题只在第一次遇到的时候对它进行求解并把答案保存起来让以后再次遇到时直接引用答案不必重新求解。动态规划算法将问题的解决方案视为一系列决策的结果二.动态规划数组思路这道题目相对前面两道题目难了不少。关键在于至多买卖两次这意味着可以买卖一次可以买卖两次也可以不买卖。接来下我用动态规划五部曲详细分析一下确定dp数组以及下标的含义一天一共就有五个状态(0)没有操作 其实我们也可以不设置这个状态(1)第一次持有股票(2)第一次不持有股票(3)第二次持有股票(4)第二次不持有股票dp[i][j]中 i表示第i天j为 [0 - 4] 五个状态dp[i][j]表示第i天状态j所剩最大现金。需要注意dp[i][1]表示的是第i天买入股票的状态并不是说一定要第i天买入股票这是很多同学容易陷入的误区。例如 dp[i][1] 并不是说 第i天一定买入股票有可能 第 i-1天 就买入了那么 dp[i][1] 延续买入股票的这个状态。2.确定递推公式达到dp[i][1]状态有两个具体操作操作一第i天买入股票了那么dp[i][1] dp[i-1][0] - prices[i]操作二第i天没有操作而是沿用前一天买入的状态即dp[i][1] dp[i - 1][1]那么dp[i][1]究竟选 dp[i-1][0] - prices[i]还是dp[i - 1][1]呢一定是选最大的所以 dp[i][1] max(dp[i-1][0] - prices[i], dp[i - 1][1]);同理dp[i][2]也有两个操作操作一第i天卖出股票了那么dp[i][2] dp[i - 1][1] prices[i]操作二第i天没有操作沿用前一天卖出股票的状态即dp[i][2] dp[i - 1][2]所以dp[i][2] max(dp[i - 1][1] prices[i], dp[i - 1][2])同理可推出剩下状态部分dp[i][3] max(dp[i - 1][3], dp[i - 1][2] - prices[i]);dp[i][4] max(dp[i - 1][4], dp[i - 1][3] prices[i]);3.dp数组如何初始化第0天没有操作这个最容易想到就是0即dp[0][0] 0;第0天做第一次买入的操作dp[0][1] -prices[0];第0天做第一次卖出的操作这个初始值应该是多少呢此时还没有买入怎么就卖出呢 其实大家可以理解当天买入当天卖出所以dp[0][2] 0;第0天第二次买入操作初始值应该是多少呢应该不少同学疑惑第一次还没买入呢怎么初始化第二次买入呢第二次买入依赖于第一次卖出的状态其实相当于第0天第一次买入了第一次卖出了然后再买入一次第二次买入那么现在手头上没有现金只要买入现金就做相应的减少。所以第二次买入操作初始化为dp[0][3] -prices[0];同理第二次卖出初始化dp[0][4] 0;4.确定遍历顺序从递归公式其实已经可以看出一定是从前向后遍历因为dp[i]依靠dp[i - 1]的数值。5.举例推导dp数组以输入[1,2,3,4,5]为例大家可以看到红色框为最后两次卖出的状态。现在最大的时候一定是卖出的状态而两次卖出的状态现金最大一定是最后一次卖出。如果想不明白的录友也可以这么理解如果第一次卖出已经是最大值了那么我们可以在当天立刻买入再立刻卖出。所以dp[4][4]已经包含了dp[4][2]的情况。也就是说第二次卖出手里所剩的钱一定是最多的。所以最终最大利润是dp[4][4]以上五部都分析完了不难写出如下代码class Solution {
public:int maxProfit(vectorint prices) {if (prices.size() 0) return 0;vectorvectorint dp(prices.size(), vectorint(5, 0));dp[0][1] -prices[0];dp[0][3] -prices[0];for (int i 1; i prices.size(); i) {dp[i][0] dp[i - 1][0];dp[i][1] max(dp[i - 1][1], dp[i - 1][0] - prices[i]);dp[i][2] max(dp[i - 1][2], dp[i - 1][1] prices[i]);dp[i][3] max(dp[i - 1][3], dp[i - 1][2] - prices[i]);dp[i][4] max(dp[i - 1][4], dp[i - 1][3] prices[i]);}return dp[prices.size() - 1][4];}
};时间复杂度O(n)空间复杂度O(n × 5)java实现class Solution {public int maxProfit(int[] prices) {int len prices.length;// 边界判断, 题目中 length 1, 所以可省去if (prices.length 0) return 0;/** 定义 5 种状态:* 0: 没有操作, 1: 第一次买入, 2: 第一次卖出, 3: 第二次买入, 4: 第二次卖出*/int[][] dp new int[len][5];dp[0][1] -prices[0];// 初始化第二次买入的状态是确保 最后结果是最多两次买卖的最大利润dp[0][3] -prices[0];for (int i 1; i len; i) {dp[i][1] Math.max(dp[i - 1][1], -prices[i]);dp[i][2] Math.max(dp[i - 1][2], dp[i][1] prices[i]);dp[i][3] Math.max(dp[i - 1][3], dp[i][2] - prices[i]);dp[i][4] Math.max(dp[i - 1][4], dp[i][3] prices[i]);}return dp[len - 1][4];}
}
