购物网站简介,为男人做购物网站,html页面跳转,排版设计技巧代码随想录第五十天 Leetcode 123. 买卖股票的最佳时机 IIILeetcode 188. 买卖股票的最佳时机 IV Leetcode 123. 买卖股票的最佳时机 III
题目链接: 买卖股票的最佳时机 III 自己的思路:想不到#xff01;#xff01;#xff01;#xff01;高维dp数组#xff01;#x… 代码随想录第五十天 Leetcode 123. 买卖股票的最佳时机 IIILeetcode 188. 买卖股票的最佳时机 IV Leetcode 123. 买卖股票的最佳时机 III
题目链接: 买卖股票的最佳时机 III 自己的思路:想不到高维dp数组
正确思路:这里和之前的都不太一样因为限制了买卖股票的次数所以我们就加大dp数组的维度动规五部曲1、dp数组的含义dp[i][0]表示一开始不操作的情况、dp[i][1]表示第一次持有不一定第i天才买入、dp[i][2]表示第一次不持有不一定第i天才卖出、dp[i][3]表示第二次持有不一定第i天才买入、dp[i][4]表示第二次不持有不一定第i天才卖出2、递推公式其实和上一题的递推公式是一样的拿一种情况来讨论dp[i][3]的情况1、当第i天不买入的时候dp[i-1][3]2、当第i天买入的时候dp[i-1][[2]-prices[i]取最大值其他的情况类似不做讨论3、dp数组初始化由于后面的都是由dp[0][:]的时候推导得到所以我们初始化dp[0][:]dp[0][0]0因为一开始的金额是0dp[0][1]-prices[0]因为一开始金额为0买入之后金额变成负的prices[0]dp[0][2]0这里可以看做是第一天买入又卖出dp[0][3]这里可以看做是第一天买入又卖出又买入dp[0][4]这里可以看做是第一天买入又卖出又买入又卖出4、遍历顺序还是和之前一样从前向后遍历5、打印dp数组主要用于debug
代码:
class Solution {public int maxProfit(int[] prices) {int length prices.length;int[][] dp new int[length][4];//dp数组初始化dp[0][0] -prices[0];dp[0][1] 0;dp[0][2] -prices[0];dp[0][3] 0;for (int i 1;ilength;i){//递推公式dp[i][0] Math.max(dp[i-1][0],-prices[i]);dp[i][1] Math.max(dp[i-1][1],dp[i][0]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]);}return dp[length-1][3];}
}Leetcode 188. 买卖股票的最佳时机 IV
题目链接: 买卖股票的最佳时机 IV 自己的思路:其实和上一题基本一样只不过广义化了一下注意点细节就可以
代码:
class Solution {public int maxProfit(int k, int[] prices) {int length prices.length;int[][] dp new int[length][2*k1];//dp数组初始化for (int i0;i2*k;i){if (i%20) dp[0][i] 0;else dp[0][i] -prices[0];}for (int i 1;iprices.length;i){//递推公式for (int j1;j2*k;j){if (j%20) dp[i][j] Math.max(dp[i-1][j],dp[i-1][j-1]prices[i]);else dp[i][j] Math.max(dp[i-1][j],dp[i-1][j-1]-prices[i]);}}return dp[length-1][2*k];}
}
