《dp補卡——買賣股票問題》

目錄

  • 121. 買賣股票的最佳時機
    • 貪心
    • dp思路
    • 滾動數組優化
  • 122. 買賣股票的最佳時機 II
  • 123. 買賣股票的最佳時機 III
  • 188. 買賣股票的最佳時機 IV
  • 309. 最佳買賣股票時機含冷凍期
  • 714. 買賣股票的最佳時機含手續費

121. 買賣股票的最佳時機

貪心

取最左最小值,取最右最大值,差值為最大利潤

class Solution {
public:int maxProfit(vector<int>& 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(vector<int>& prices) {int n = prices.size();vector<vector<int>> dp(n,vector<int>(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(vector<int>& prices) {int n = prices.size();vector<vector<int>> dp(2,vector<int>(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(vector<int>& prices) {int n = prices.size();vector<vector<int>> dp(2,vector<int>(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(vector<int>& prices) {int n = prices.size();vector<vector<int>> dp(n,vector<int>(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*k+1.

vector<vector<int>> dp(prices.size(),vector<int>(2*k+1,0));

step2:

for(int j = 0; j < 2 * k - 1; j+=2)
{//奇數,說明買入dp[i][j+1] = max(dp[i-1][j+1],dp[i-1][j] - prices[i]);//偶數,說明賣出dp[i][j+2] = max(dp[i-1][j+2],dp[i-1][j+1] + 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, vector<int>& prices) {int n = prices.size();if(n == 0 || k == 0) return 0; vector<vector<int>> dp(n,vector<int>(k*2+1,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][j+1] = max(dp[i-1][j+1],dp[i-1][j]-prices[i]);dp[i][j+2] = max(dp[i-1][j+2],dp[i-1][j+1]+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(vector<int>& prices) {int n = prices.size();vector<vector<int>> dp(n,vector<int>(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(vector<int>& prices, int fee) {int n = prices.size();vector<vector<int>> dp(2,vector<int>(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];}
};

本文來自互聯網用戶投稿,該文觀點僅代表作者本人,不代表本站立場。本站僅提供信息存儲空間服務,不擁有所有權,不承擔相關法律責任。
如若轉載,請注明出處:http://www.pswp.cn/news/377094.shtml
繁體地址,請注明出處:http://hk.pswp.cn/news/377094.shtml
英文地址,請注明出處:http://en.pswp.cn/news/377094.shtml

如若內容造成侵權/違法違規/事實不符,請聯系多彩編程網進行投訴反饋email:809451989@qq.com,一經查實,立即刪除!

相關文章

oo0ooo0ooo0oo_OoO的完整形式是什么?

oo0ooo0ooo0ooOoO&#xff1a;外出 (OoO: Out of Office) OoO is an abbreviation of "Out of Office". OoO是“不在辦公室”的縮寫。 It is an expression, which is commonly used in the Gmail platform. It is written in the body or the subject of the email…

SP2010開發和VS2010專家食譜--第三章節--高級工作流(2)--為沙盒解決方案創建自定義活動...

盡管沙河解決方案功能有限&#xff0c;你仍然可以開發自定義活動&#xff0c;在SharePoint Designer中使用而不用改變web.config或添加.ACTION文件到根文件夾。 轉載于:https://www.cnblogs.com/crazygolf/p/3856795.html

sql where 1=1和 0=1 的作用

where 11; 這個條件始終為True&#xff0c;在不定數量查詢條件情況下&#xff0c;11可以很方便的規范語句。 一、不用where 11 在多條件查詢中的困擾 舉個例子&#xff0c;如果您做查詢頁面&#xff0c;并且&#xff0c;可查詢的選項有多個&#xff0c;同時&#xff0c;還讓用戶…

j@2ff4f00f_J4F的完整形式是什么?

j2ff4f00fJ4F&#xff1a;只是為了好玩 (J4F: Just For Fun) J4F is an abbreviation of "Just For Fun". J4F是“ Just For Fun”的縮寫 。 It is an expression, which is commonly used in messaging or chatting on social media networking sites like Faceboo…

《dp補卡——子序列問題》

目錄300. 最長遞增子序列674. 最長連續遞增序列718. 最長重復子數組1143. 最長公共子序列53. 最大子序和392. 判斷子序列115. 不同的子序列583. 兩個字符串的刪除操作72. 編輯距離647. 回文子串 &#xff08;與 5.最長回文子串思路差不多&#xff09;516. 最長回文子序列300. 最…

[LeetCode] Maximal Rectangle

Given a 2D binary matrix filled with 0s and 1s, find the largest rectangle containing all ones and return its area. 在做 Largest Rectangle in Histogram的時候有人說可以用在這題&#xff0c;看了一下還真是&#xff0c;以每行為x軸&#xff0c;每列往上累計的連續的…

什么是alpha測試_什么是ALPHA?

什么是alpha測試Α (ALPHA) Alpha is the first and foremost letter of the Greek alphabet. In the classification of Greek numerals or numbers, it constitutes a value of 1. Alpha是希臘字母的第一個也是最重要的字母 。 在希臘數字或希臘數字的分類中&#xff0c;它的…

《leetcode : 647. 回文子串 思考分析雙指針解法》

647. 回文子串 如何確定是回文串&#xff1a; 找中心然后往兩邊擴散&#xff0c;判斷是否對稱即可。 在遍歷中心點的時候&#xff0c;注意中心點可以是一個元素也可以是兩個元素。 class Solution { public:int cal_two_extend(const string& s,int i,int j,int n){int re…

天草初級班(3)

算術運算指令算術運算指令是反映CPU計算能力的一組指令&#xff0c;也是編程時經常使用的一組指令。它包括&#xff1a;加、減、乘、除及其相關的輔助指令。 該組指令的操作數可以是8位、16位和32位(80386)。當存儲單元是該類指令的操作數時&#xff0c;該操作數的尋址方式可以…

4.3.3版本之引擎bug

bug描述&#xff1a;   IOS設備上&#xff0c;當使用WWW www WWW.LoadFromCacheOrDownload(url, verNum); 下載資源時&#xff0c;第一次下載某個資源&#xff0c;www.assetBundle必定為空。 解決辦法&#xff1a;   引擎版本降到4.3.2或者升到4.3.4或更高。 這個bug絕對是…

sml完整形式_411的完整形式是什么?

sml完整形式411&#xff1a;信息 (411: Information) 411 is an abbreviation of “Information". 411是“信息”的縮寫 。 It is an expression, which is commonly used in messaging or chatting on social media networking sites like Facebook, Yahoo Messenger, a…

php 檢測用戶是否關閉瀏覽器

1、例子1 echo str_repeat(" ",3000);ignore_user_abort(true); mylog(online);while (true) {/** 1、程序正常結束 connection_status 0* 2、點擊瀏覽器“停止”按鈕 connection_status 1* 3、超時 connection_status 2*/echo "test<br>\n&qu…

explain用法

explain用法 EXPLAIN SELECT …… 變體&#xff1a; 1. EXPLAIN EXTENDED SELECT …… 將執行計劃“反編譯”成SELECT語句&#xff0c;運行SHOW WARNINGS 可得到被MySQL優化器優化后的查詢語句 2. EXPLAIN PARTITIONS SELECT …… 用于分區表的EXPLAIN 執行計劃包含的信息 id…

《位運算技巧以及Leetcode的一些位運算題目》

目錄技巧練習位運算[461. 漢明距離](https://leetcode-cn.com/problems/hamming-distance/)[190. 顛倒二進制位](https://leetcode-cn.com/problems/reverse-bits/)[136. 只出現一次的數字](https://leetcode-cn.com/problems/single-number/)[260. 只出現一次的數字 III](http…

linux讀取配置文件(C語言版)

一個通用的linux系統中C語言版讀取配置文件的函數。 #include <stdio.h> #include <stdlib.h> #include <string.h> #include <assert.h> #include <errno.h>#define KEYVALLEN 100/* 刪除左邊的空格 */ char * l_trim(char * szOutput, con…

java 范圍搜尋要怎么弄_搜索范圍

java 范圍搜尋要怎么弄Problem statement: 問題陳述&#xff1a; Given an array of integers nums sorted in ascending order, find the starting and ending position of a given target value. 給定一個以升序排列的整數nums數組&#xff0c;請找到給定目標值的開始和結束…

boa + ajax + cgi ajax請求cgi

最近公司要做一個通訊管理機,然后需要和另外一個同事一起做,我們需要用到boaAjaxCGI,以前沒試過與CGI交互,一開始發現問題挺大的,用ajax請求cgi,總是不返回數據,又或者請求回來的是cgi的源碼,后來發現,通過本地IIS或者直接打開html頁面請求的,返回來的都是cgi的源碼或者返回失敗…

《DBNotes:single_table訪問方法、MRR多范圍讀取優化、索引合并》

目錄single_table訪問方法constrefref_or_nullrangeindexallMRR多范圍讀取優化索引合并intersectionunionsort-unionsingle_table訪問方法 const 在主鍵列或者unique二級索引與一個常數進行等值比較時才有效。 如果主鍵或者unique二級索引的索引列由多個列構成&#xff0c;則…

怎樣通過命令管理Windows7桌面防火墻

&#xff08;1&#xff09;啟用桌面防火墻netsh advfirewall set allprofiles state on&#xff08;2&#xff09;設置默認輸入和輸出策略netsh advfirewall set allprofiles firewallpolicy allowinbound,allowoutbound以上是設置為允許&#xff0c;如果設置為拒絕使用blockin…

ruby推送示例_Ruby for循環示例

ruby推送示例for循環 (The for loop) In programming, for loop is a kind of iteration statement which allows the block to be iterated repeatedly as long as the specified condition is not met or a specific number of times that the programmer knows beforehand. …