苏州做网站便宜的公司哪家好,网页设计师的主要职责,如何做游戏试玩网站,无线新闻台直播app下载目录121. 买卖股票的最佳时机贪心dp思路滚动数组优化122. 买卖股票的最佳时机 II123. 买卖股票的最佳时机 III188. 买卖股票的最佳时机 IV309. 最佳买卖股票时机含冷冻期714. 买卖股票的最佳时机含手续费121. 买卖股票的最佳时机
贪心
取最左最小值#xff0c;取最右最大值取最右最大值差值为最大利润
class Solution {
public:int maxProfit(vectorint prices) {int n prices.size();int minprice prices[0];int maxpro 0;for(int i 1; i n; i){minprice min(prices[i],minprice);maxpro max(prices[i]-minprice,maxpro);}return maxpro;}
};dp思路
step1:dp[i][0]表示第i天持有股票最大所得现金。本题中只能买卖一次所以买入后金额为-price[i]。 dp[i][1]表示第i天不持有股票最大所得现金。持有不等同于买入。 step2: 如果第i天持有股票dp[i][0]可以由两个状态得到。 case1:第i-1持有股票保持现状dp[i][0] dp[i-1][0] case2:第i天买入股票所得现金就是买入今天的股票后所得现金。即dp[i][0] -price[i] dp[i][0] max(dp[i-1][0],-price[i]); 如果第i天不持有股票dp[i][1]可以由两个状态得到。 case1: 第i-1不持有股票保持现状dp[i][1] dp[i-1][1] case2: 第i-1持有股票第i天卖出,dp[i][1] dp[i-1][0] price[i] dp[i][1] max(dp[i-1][1],dp[i-1][0]price[i]) step3: 初始状态为dp[0][0]:第0天持有股票的金额 -prices[0] dp[0][1]第0天不持有股票的金额 0 最终结果dp[n][1]而不是dp[n][0],是因为最终必须要把股票卖出才能有收益。不卖出一定更亏。
class Solution {
public:int maxProfit(vectorint prices) {int n prices.size();vectorvectorint dp(n,vectorint(2,0));dp[0][0] -prices[0];dp[0][1] 0;for(int i 1; i n; i){//持有dp[i][0] max(dp[i-1][0],-prices[i]);//不持有dp[i][1] max(dp[i-1][1],dp[i-1][0]prices[i]);}return dp[n-1][1];}
};滚动数组优化
由于只用到了dp[i] 与dp[i-1]两个状态所以只需一个2 * 2的数组即可。
class Solution {
public:int maxProfit(vectorint prices) {int n prices.size();vectorvectorint dp(2,vectorint(2,0));dp[0][0] -prices[0];dp[0][1] 0;for(int i 1; i n; i){//持有dp[i % 2][0] max(dp[(i-1)%2][0],-prices[i]);//不持有dp[i % 2][1] max(dp[(i-1)%2][1],dp[(i-1)%2][0]prices[i]);}return dp[(n-1)%2][1];}
};122. 买卖股票的最佳时机 II
dp[i][0]:第i天持有股票获取的最大现金 dp[i][1]:第i天不持有股票所得的最多现金 如果第i天持有股票则dp[i][0]可以由两个状态推导; case1:第i-1天就持有股票保持现状则dp[i][0] dp[i-1][0] case2:第i天买入股票现金则为昨天不持有股票所得现金减去今天股票价格dp[i][0] dp[i-1][1] - prices[i] 如果第i天不持有股票则dp[i][1]可以由两个状态推导 case1第i-1天不持有股票保持现状dp[i][1] dp[i-1][1] case2第i-1天持有股票第i天卖出dp[i][1] dp[i-1][0] prices[i]
class Solution {
public:int maxProfit(vectorint prices) {int n prices.size();vectorvectorint dp(2,vectorint(2,0));dp[0][0] -prices[0];dp[0][1] 0;for(int i 1; i n; i){dp[i%2][0] max(dp[(i-1)%2][0],dp[(i-1)%2][1]-prices[i]);dp[i%2][1] max(dp[(i-1)%2][1],dp[(i-1)%2][0]prices[i]);}return dp[(n-1)%2][1];}
};123. 买卖股票的最佳时机 III
至多买卖两次即可以买卖一次也可以买卖两次也可以不买卖。 每一天由五个状态 0、没有操作 1、第一次买入 2、第一次卖出 3、第二次买入 4、第二次卖出 dp[i][j]:i表示第i天j为[0-4]五个状态dp[i][j]表示第i天状态j所剩最大现金。
2、确定递推公式 举例dp[i][1]:表示第i天买入股票的状态并不是说一定要第i天买入股票。 达到dp[i][1]状态有两个具体操作 case1第i天买入股票那么dp[i][1] dp[i-1][0] - prices[i] case2第i天没有操作那么dp[i][1] dp[i-1][1] dp[i-1][1] max(dp[i-1][0]-prices[i],dp[i-1][1]); 同理dp[i][2]也有两个操作 case1第i天卖出股票了那么dp[i][2] dp[i-1][1] prices[i] case2第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]也有两个操作 case1第i天买入股票dp[i][3] dp[i-1][2] - prices[i] case2第i天没有操作沿用前一天买入股票的状态即dp[i][3] dp[i-1][3] 同理dp[i][4]也有两个操作 case1第i天卖出股票dp[i][4] dp[i-1][3] prices[i] case2第i天没有操作沿用前一天卖出股票的状态即dp[i][4] dp[i-1][4] 那么如何初始化呢 第0天没有操作的话dp[0][0] 0 第0天做第一次买入操作的话dp[0][1] -prices[0] 第0天做第一次卖出的操作这个初始值为0。 第0天第二次买入不管几次手头上没有钱只能减少dp[0][3] -prices[0] 第0天第二次卖出dp[0][4] 0
class Solution {
public:int maxProfit(vectorint prices) {int n prices.size();vectorvectorint dp(n,vectorint(5,0));//dp[0][0] 0;dp[0][1] -prices[0];//dp[0][2] 0;dp[0][3] -prices[0];//dp[0][4] 0;for(int i 1; i n; 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[n-1][4];}
};188. 买卖股票的最佳时机 IV
step1: 这一题为上一题的进阶版本定义二维dp数组。 使用二维数组dp[i][j]第i天的状态为j所剩下的最大现金是dp[i][j] j的状态表示为 0不操作、1第一次买入、2第一次卖出、… 除了0以外偶数就是卖出奇数就是买入。因为是最多有k笔交易所以j的范围就定义为2*k1.
vectorvectorint dp(prices.size(),vectorint(2*k1,0));step2:
for(int j 0; j 2 * k - 1; j2)
{//奇数说明买入dp[i][j1] max(dp[i-1][j1],dp[i-1][j] - prices[i]);//偶数说明卖出dp[i][j2] max(dp[i-1][j2],dp[i-1][j1] prices[i]);
}step3: 初始化只要是买入操作现金就会相应减少卖出操作初值均为0
for(int j 1; j 2*k; j 2)
{dp[0][j] -prices[0];
}AC代码
class Solution {
public:int maxProfit(int k, vectorint prices) {int n prices.size();if(n 0 || k 0) return 0; vectorvectorint dp(n,vectorint(k*21,0));for(int i 1; i 2*k; i 2)dp[0][i] -prices[0];for(int i 1; i n; i){for(int j 0; j 2 * k - 2; j 2){dp[i][j1] max(dp[i-1][j1],dp[i-1][j]-prices[i]);dp[i][j2] max(dp[i-1][j2],dp[i-1][j1]prices[i]);}}return dp[n-1][2*k];}
};309. 最佳买卖股票时机含冷冻期
状态一买入股票状态可能是今天买入的也有可能是之前就买入了然后没有操作 对于卖出股票状态有两种 状态二两天前就卖出了股票度过了冷冻期然后一直没有操作今天仍然保持卖出股票状态 状态三今天卖出了股票 状态四今天为冷冻期状态但冷冻期状态不可持续只有一天 递推公式如下 到达买入股票状态(状态一)即dp[i][0]有两个具体操作 case1前一天就是这个状态今天沿用该状态dp[i][0] dp[i-1][0] case2今天买入有两种情况(状态四) 前一天是冷冻期前一天是保持卖出股票的状态(状态二),这两个情况今天都有可能买入 即dp[i][0] max(dp[i-1][0],max(dp[i-1][3],dp[i-1][1])-prices[i]) 到达保持卖出状态(状态二)即dp[i][1]有两个具体操作 case1前一天就是状态二沿用该状态 case2前一天是冷冻期状态四 dp[i][1] max(dp[i-1][1],dp[i-1][3]) 到达今天卖出股票状态(状态三)只有一个状态前一天是状态一然后今天卖出 dp[i][2] dp[i-1][0] prices[i] 到达冷冻期状态(状态四)只有一个状态前一天刚卖出股票 dp[i][3] dp[i-1][2] 综上的递推代码为
dp[i][0] max(dp[i-1][0],max(dp[i-1][3],dp[i-1][1])-prices[i]);
dp[i][1] max(dp[i-1][1],dp[i-1][3]);
dp[i][2] dp[i-1][0] prices[i];
dp[i][3] dp[i-1][2];关于dp数组的初始化 状态一持有股票那么dp[0][0] -prices[0] 状态二保持卖出状态dp[0][1] 0 状态三刚卖出股票同样不会有收入dp[0][2] 0 状态四冷冻期dp[0][3] 0 最后的结果是从状态二到状态四中选取最大值。
class Solution {
public:int maxProfit(vectorint prices) {int n prices.size();vectorvectorint dp(n,vectorint(4,0));dp[0][0] -prices[0];for(int i 1; i n; i){dp[i][0] max(dp[i-1][0],max(dp[i-1][1],dp[i-1][3])-prices[i]);dp[i][1] max(dp[i-1][1],dp[i-1][3]);dp[i][2] dp[i-1][0] prices[i];dp[i][3] dp[i-1][2];}return max(dp[n-1][1],max(dp[n-1][2],dp[n-1][3]));}
};714. 买卖股票的最佳时机含手续费
与122. 买卖股票的最佳时机 II相比多减去操作费用。
class Solution {
public:int maxProfit(vectorint prices, int fee) {int n prices.size();vectorvectorint dp(2,vectorint(2,0));dp[0][0] -prices[0];dp[0][1] 0;for(int i 1; i n; i){//当天持有dp[i%2][0] max(dp[(i-1)%2][0],dp[(i-1)%2][1]-prices[i]);//当天不持有dp[i%2][1] max(dp[(i-1)%2][1],dp[(i-1)%2][0]prices[i]-fee);}return dp[(n-1)%2][1];}
};
