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因为一开始的金额是0;dp[0][1]=-prices[0]因为一开始金额为0,买入之后金额变成负的prices[0];dp[0][2]=0这里可以看做是第一天买入又卖出;dp[0][3]这里可以看做是第一天买入又卖出又买入;dp[0][4]这里可以看做是第一天买入又卖出又买入又卖出!!!4、遍历顺序:还是和之前一样从前向后遍历;5、打印dp数组:主要用于debug!!!!
代码:文章来源地址https://www.toymoban.com/news/detail-679446.html
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;i<length;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
自己的思路:其实和上一题基本一样,只不过广义化了一下,注意点细节就可以!!!!!文章来源:https://www.toymoban.com/news/detail-679446.html
代码:
class Solution {
public int maxProfit(int k, int[] prices) {
int length = prices.length;
int[][] dp = new int[length][2*k+1];
//dp数组初始化
for (int i=0;i<=2*k;i++){
if (i%2==0) dp[0][i] = 0;
else dp[0][i] = -prices[0];
}
for (int i =1;i<prices.length;i++){
//递推公式
for (int j=1;j<=2*k;j++){
if (j%2==0) 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];
}
}
到了这里,关于代码随想录第五十天的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!