買賣股票的最佳時機

分析

根據題意可知，我們只需要找出來一個最小價格的股票和一個最大價格的股票，并且最小價格的股票出現在最大價格的股票之前。

如果嘗試使用暴力解法，時間復雜度為O(N^2)，對于題目中給的長度，顯然是會超時的，因此我們需要另尋它法。

我們可以使用一次遍歷，在經過每個值時，計算出包含該值之前的股票的最低價格和最大利潤，該種方法的時間復雜度為O(N)，顯然是可解的。

初始化：由于在確定價格最小值時涉及到min求最小值，而且根據題目所給價格的范圍，我們可以使用 0x3f3f3f3f 來初始化minprice；根據題意，由于利潤最小為0，不涉及到為負的情況，因此初始化 profit 為0即可。

填表順序：從左到右。

返回值：profit

代碼

class Solution {
public:int maxProfit(vector<int>& prices) {int n=prices.size();int profit=0,minprice=0x3f3f3f3f;for(int price:prices){profit=max(profit,price-minprice);minprice=min(price,minprice);}return profit;}
};

買賣芯片的最佳時機

分析

根據題意，只需找到一個最低價格和一個最高價格，并且最低價格出現在最高價格之前，顯然與上面的題意是一樣的，解法顯而易見也是一樣的。

代碼

class Solution {
public:int bestTiming(vector<int>& prices) {int n=prices.size();int profit=0,minprice=0x3f3f3f3f;for(int price:prices){profit=max(profit,price-minprice);minprice=min(price,minprice);}return profit;}
};

買賣股票的最佳時機II

分析

如果以以往經驗，對于本題，我們可以定義一個 dp 表，dp[i] 表示以 i 位置為結尾，能獲取的最大利潤，即：

由于題目中涉及到該天“買股票”和“賣股票”的問題，因此，僅僅使用一維 dp 是不能解決問題的，因此可以嘗試使用二維 dp 來解決，dp[i][0] 表示手里沒股票的時候能獲取的最大利潤，dp[i][1]表示手里有股票的時候能獲取的最大利潤（易知這里說的有股票指的是“一張股票”）。

狀態轉移方程：dp[i][0]=max(dp[i-1][0],dp[i-1][1]+prices[i])

? ? ? ? ? ? ? ? ? ? ? ? ?dp[i][1]=max(dp[i-1][1],dp[i-1][0]-prices[i])

初始化：由于只會用到前一行的值，因此只需初始化第一行的值即可，dp[0][0]表示第1天手里沒股票的最大利潤，為0；dp[0][1]表示第一天手里有股票的最大利潤，為 -prices[0]。

填表順序：從上到下。

返回值：dp[n-1][0]，因為最后一天手里有股票肯定是比最后一天沒股票要虧。

代碼

class Solution {
public:int maxProfit(vector<int>& prices) {int n=prices.size();vector<vector<int>> dp(n,vector<int>(2));dp[0][1]=-prices[0];for(int i=1;i<n;i++){dp[i][0]=max(dp[i-1][0],dp[i-1][1]+prices[i]);dp[i][1]=max(dp[i-1][1],dp[i-1][0]-prices[i]);}return dp[n-1][0];}
};

買賣股票的最佳時機含手續費

分析

?如果以以往經驗，對于本題，我們可以定義一個 dp 表，dp[i] 表示以 i 位置為結尾，能獲取的最大利潤，即：

由于題目涉及到該天“買股票”和“賣股票”這兩種情況，顯然只表示該天為結尾能獲取的最大利潤，是非常模糊的，那么問題也得不到解決。

因此考慮使用二維 dp 來解決問題，dp[i][0]表示第 i 天手里沒股票的時候能獲取的最大利潤；dp[i][1]表示第 i 天手里有股票的時候能獲取的最大利潤（顯然，根據題意，這里所說的有股票指的是“一張股票”）。

狀態轉移方程：dp[i][0]=max(dp[i-1][0],dp[i-1][1]+prices[i]-fee);

? ? ? ? ? ? ? ? ? ? ? ? ?dp[i][1]=max(dp[i-1][1],dp[i-1][0]-prices[i]);

初始化：由于只會用到前一行的值，因此只需初始化第一行的值即可，dp[0][0]表示第1天手里沒股票的最大利潤，為0；dp[0][1]表示第一天手里有股票的最大利潤，為 -prices[0]。

填表順序：從上到下。

返回值：dp[n-1][0]，因為最后一天手里有股票肯定是比最后一天沒股票要虧。

解法一

代碼

class Solution {
public:int maxProfit(vector<int>& prices, int fee) {int n=prices.size();vector<vector<int>> dp(n,vector<int>(2));//dp[i][0] 表示沒股票的最大利潤//dp[i][1] 表示有股票的最大利潤dp[0][1]=-prices[0];for(int i=1;i<n;i++){dp[i][0]=max(dp[i-1][0],dp[i-1][1]+prices[i]-fee);dp[i][1]=max(dp[i-1][1],dp[i-1][0]-prices[i]);}return dp[n-1][0];}
};

解法二

根據解法一的狀態轉移方程可知，每一次填寫只會用到前一行的兩個值，因此我們可以只定義幾個變量來解決問題。

代碼

class Solution {
public:int maxProfit(vector<int>& prices, int fee) {int n=prices.size();int a=0,b=-prices[0];//a 表示沒股票的最大利潤//b 表示有股票的最大利潤for(int i=1;i<n;i++){int a1=max(a,b+prices[i]-fee);int b1=max(b,a-prices[i]);a=a1,b=b1;}return a;}
};

解法三（貪心）

仔細分析前兩種解法，不難發現，都是在賣出股票的時候進行決策優劣的，我們不妨嘗試在買入股票的時候進行優劣的決策。

定義buy表示買入價格（含手續費），當某天價格+手續費 < buy 的時候，表示我們可以用更低成本賣股票，則更新 buy=prices[i]+fee。

定義profit表示能獲取的最大利潤，當prices[i] > buy的時候，我們會賣出股票，但是這里需要注意的是，如果我們這個時候賣出股票，可能不是最優的，因為可能之后的價格更高，即一張股票可以賺更高的利潤，因此我們可以嘗試以下策略：先賣掉，并把 buy 更新為 prices[i]，那么在之后遇到更高價格之后，只需加上差價即可，即：我們是提供了一種“可以反悔”的操作。

代碼

class Solution {
public:int maxProfit(vector<int>& prices, int fee) {int n=prices.size();int buy=prices[0]+fee;int profit=0;for(int i=1;i<n;i++){if(prices[i]+fee < buy)buy=prices[i]+fee;else if(prices[i] > buy){profit+=prices[i]-buy;buy=prices[i];}}return profit;}
};

買賣股票的最佳時期含冷凍期

分析

??如果以以往經驗，對于本題，我們可以定義一個 dp 表，dp[i] 表示以 i 位置為結尾，能獲取的最大利潤，即：

由于題目涉及到該天“買股票”，“賣股票”和“冷凍期”這三種情況，顯然只表示該天為結尾能獲取的最大利潤，是非常模糊的，那么問題也得不到解決。

因此考慮使用二維 dp 來解決問題，dp[i][0]表示第 i 天手里有股票的時候能獲取的最大利潤（顯然，根據題意，這里所說的有股票指的是“一張股票”）；dp[i][1]表示手里沒股票，當天處于冷凍期的最大利潤；dp[i][2]表示手里沒股票，當天不處于冷凍期的時候所能獲取的最大利潤。

狀態轉移方程：dp[i][0]=max(dp[i-1][0],dp[i-1][2]-prices[i]);

? ? ? ? ? ? ? ? ? ? ? ? ?dp[i][1]=dp[i-1][0]+prices[i];

? ? ? ? ? ? ? ? ? ? ? ? ?dp[i][2]=max(dp[i-1][1],dp[i-1][2]);

初始化：根據狀態轉移方程可知，每次填值只會用到上一行的值，因此只需初始化第一行即可，

? ? ? ? ? ? ? dp[0][0]= -prices[0]，dp[0][1]=0，dp[0][2]=0。

填表順序：從上到下。

返回值：max(dp[n-1][1],dp[n-1][2]).因為最后一天手里有股票肯定是比最后一天手里沒股票要虧的.

解法一

代碼

class Solution {
public:int maxProfit(vector<int>& prices) {int n=prices.size();vector<vector<int>> dp(n,vector<int>(3));dp[0][0]=-prices[0];//dp[i][0] 手里有股票的最大利潤//dp[i][1] 手里沒股票，處于冷凍期的最大利潤//dp[i][2] 手里沒股票，不處于冷凍期的最大利潤for(int i=1;i<n;i++){dp[i][0]=max(dp[i-1][0],dp[i-1][2]-prices[i]);dp[i][1]=dp[i-1][0]+prices[i];dp[i][2]=max(dp[i-1][1],dp[i-1][2]);}return max(dp[n-1][1],dp[n-1][2]);}
};

解法二

根據解法一可知，每次填值只會用到上一行的三個值，因此可以嘗試用幾個變量來解決，時間復雜度為O(N)。

代碼

class Solution {
public:int maxProfit(vector<int>& prices) {int n=prices.size();int a=-prices[0],b=0,c=0;//a 手里有股票的最大利潤//b 手里沒股票，處于冷凍期的最大利潤//c 手里沒股票，不處于冷凍期的最大利潤for(int i=1;i<n;i++){int a1=max(a,c-prices[i]);int b1=a+prices[i];int c1=max(b,c);a=a1,b=b1,c=c1;}return max(b,c);}
};

買賣股票的最佳時機III

分析

???如果以以往經驗，對于本題，我們可以定義一個 dp 表，dp[i] 表示以 i 位置為結尾，能獲取的最大利潤，即：

由于該題涉及“買股票”，“賣股票”和“交易次數”的問題，顯然使用一維dp是不能解決問題的。

我們可以使用三維 dp 來解決，dp[i][j][k]，i 表示第 i 天，j 表示處于手里有股票還是沒股票，k 表示已交易次數，這樣看來，三維的有點頭疼。

我們不妨可以使用兩個二維dp來解決，f[i][j]表示手里沒股票，已交易 j 次能獲取的最大利潤，g[i][j]表示手里有股票，已交易 j 次能獲取的最大利潤。

狀態轉移方程：f[i][j]=max(f[i-1][[j]，g[i-1][j-1]+prices[i])【注意：使用g[i-1][j-1]須滿足 j >=1】

? ? ? ? ? ? ? ? ? ? ? ? ?g[i][j]=max(g[i-1][j]，f[i-1][j]-prices[i]).

初始化：對于f[i][j]來說，會用到上一行的值，因此只需初始化第一行即可，由于第一行表示第一天，因此最多交易0次，對于高于0次的情況并不可能出現，初始化為 -0x3f3f3f3f.

? ? ? ? ? ? ? 對于g[i][j]來說，會用到上一行的值，也可能用到前一行前一列的值（左上方）【因此不需要初始化】

填表順序：從上到下，從左到右。

返回值：f[i][j]里面的最大值。

代碼

class Solution {
public:int maxProfit(vector<int>& prices) {int n=prices.size();vector<vector<int>> f(n,vector<int>(3,-0x3f3f3f3f));vector<vector<int>> g(n,vector<int>(3,-0x3f3f3f3f));//f[i][j] 表示沒股票的時候，已經交易j次，獲取的最大利潤//g[i][j] 表示有股票的時候，已經交易j次，獲取的最大利潤f[0][0]=0,g[0][0]=-prices[0];for(int i=1;i<n;i++){for(int j=0;j<=2;j++){f[i][j]=f[i-1][j];if(j>=1)f[i][j]=max(f[i][j],g[i-1][j-1]+prices[i]);g[i][j]=max(g[i-1][j],f[i-1][j]-prices[i]);}}return *max_element(f[n-1].begin(),f[n-1].end());}
};

買賣股票的最佳時機IV

分析

這道題與上一道題相比，差異之處為：上一道題限制交易次數最多為兩次，本題限制交易次數最多為k次，所以解法和代碼同上一道題幾乎? ? 如出一轍。

???如果以以往經驗，對于本題，我們可以定義一個 dp 表，dp[i] 表示以 i 位置為結尾，能獲取的最大利潤，即：

由于該題涉及“買股票”，“賣股票”和“交易次數”的問題，顯然使用一維dp是不能解決問題的。

我們可以使用三維 dp 來解決，dp[i][j][k]，i 表示第 i 天，j 表示處于手里有股票還是沒股票，k 表示已交易次數，這樣看來，三維的有點頭疼。

我們不妨可以使用兩個二維dp來解決，f[i][j]表示手里沒股票，已交易 j 次能獲取的最大利潤，g[i][j]表示手里有股票，已交易 j 次能獲取的最大利潤。

狀態轉移方程：f[i][j]=max(f[i-1][[j]，g[i-1][j-1]+prices[i])【注意：使用g[i-1][j-1]須滿足 j >=1】

? ? ? ? ? ? ? ? ? ? ? ? ?g[i][j]=max(g[i-1][j]，f[i-1][j]-prices[i]).

初始化：對于f[i][j]來說，會用到上一行的值，因此只需初始化第一行即可，由于第一行表示第一天，因此最多交易0次，對于高于0次的情況并不可能出現，初始化為 -0x3f3f3f3f.

? ? ? ? ? ? ? 對于g[i][j]來說，會用到上一行的值，也可能用到前一行前一列的值（左上方）【因此不需要初始化】

填表順序：從上到下，從左到右。

返回值：f[i][j]里面的最大值。

代碼

class Solution {
public:int maxProfit(int k, vector<int>& prices) {int n=prices.size();vector<vector<int>> f(n,vector<int>(k+1,-0x3f3f3f3f));vector<vector<int>> g(n,vector<int>(k+1,-0x3f3f3f3f));//f[i][j] 表示沒股票的時候，已經交易j次，獲取的最大利潤//g[i][j] 表示有股票的時候，已經交易j次，獲取的最大利潤f[0][0]=0,g[0][0]=-prices[0];for(int i=1;i<n;i++){for(int j=0;j<=k;j++){f[i][j]=f[i-1][j];if(j>=1)f[i][j]=max(f[i][j],g[i-1][j-1]+prices[i]);g[i][j]=max(g[i-1][j],f[i-1][j]-prices[i]);}}return *max_element(f[n-1].begin(),f[n-1].end());}
};