??前言
動態(tài)規(guī)劃相關(guān)題目都可以參考以下五個步驟進行解答：
-
狀態(tài)表示
-
狀態(tài)轉(zhuǎn)移?程
-
初始化
-
填表順序
-
返回值
后面題的解答思路也將按照這五個步驟進行講解。
??買賣股票的最佳時機含冷凍期
??題目描述
給定一個整數(shù)數(shù)組prices，其中第 prices[i] 表示第 i 天的股票價格
設(shè)計一個算法計算出最大利潤。在滿足以下約束條件下，你可以盡可能地完成更多的交易（多次買賣一支股票）:
賣出股票后，你無法在第二天買入股票 (即冷凍期為 1 天)。
注意：你不能同時參與多筆交易（你必須在再次購買前出售掉之前的股票）。
- 示例 1:
輸入: prices = [1,2,3,0,2]
輸出: 3
解釋: 對應(yīng)的交易狀態(tài)為: [買入, 賣出, 冷凍期, 買入, 賣出] - 示例 2:
輸入: prices = [1]
輸出: 0
class Solution {
public int maxProfit(int[] prices) {
}
}
??算法思路：
??狀態(tài)表示：
對于線性dp ，我們可以?「經(jīng)驗+題?要求」來定義狀態(tài)表示：
- 以某個位置為結(jié)尾…；
- 以某個位置為起點…。
這里我們選擇比較常?的?式，以某個位置為結(jié)尾，結(jié)合題目要求，定義?個狀態(tài)表?：
由于有「買?」「可交易」「冷凍期」三個狀態(tài)，因此我們可以選擇?三個數(shù)組，其中：
- dp[i][0] 表?：第 i 天結(jié)束后，處于「買?」?fàn)顟B(tài)，此時的最?利潤；
- dp[i][1]表?：第 i 天結(jié)束后，處于「可交易」?fàn)顟B(tài)，此時的最?利潤；
- dp[i][2] 表?：第 i 天結(jié)束后，處于「冷凍期」?fàn)顟B(tài)，此時的最?利潤。
??狀態(tài)轉(zhuǎn)移方程：
我們要謹(jǐn)記規(guī)則：
- 處于「買?」?fàn)顟B(tài)的時候，我們現(xiàn)在有股票，此時不能買股票，只能繼續(xù)持有股票，或者賣出股票；
- 處于「賣出」?fàn)顟B(tài)的時候：
- 如果「在冷凍期」，不能買?；
- 如果「不在冷凍期」，才能買?。
對于 dp[i][0] ，我們有「兩種情況」能到達(dá)這個狀態(tài)：
- 在 i - 1 天持有股票，此時最?收益應(yīng)該和 i - 1 天的保持?致： dp[i - 1][0] ；
- 在 i 天買?股票，那我們應(yīng)該選擇 i - 1 天不在冷凍期的時候買?，由于買?需要花錢，所以此時最?收益為： dp[i - 1][1] - prices[i]
兩種情況應(yīng)取最?值，因此： dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] - prices[i]) 。
對于 dp[i][1] ，我們有「兩種情況」能到達(dá)這個狀態(tài)：
- 在 i - 1 天的時候，已經(jīng)處于冷凍期，然后啥也不?到第 i 天，此時對應(yīng)的狀態(tài)為：dp[i - 1][2] ；
- 在 i - 1 天的時候，?上沒有股票，也不在冷凍期，但是依舊啥也不干到第 i 天，此時對應(yīng)的狀態(tài)為 dp[i - 1][1] ；
兩種情況應(yīng)取最?值，因此： dp[i][1] = max(dp[i - 1][1], dp[i - 1][2]) 。
對于 dp[1][i] ，我們只有「?種情況」能到達(dá)這個狀態(tài)：
- 在 i - 1 天的時候，賣出股票。
- 因此對應(yīng)的狀態(tài)轉(zhuǎn)移為： dp[i][2] = dp[i - 1][0] + prices[i]
??初始化：
三種狀態(tài)都會用到前?個位置的值，因此需要初始化每?行的第?個位置：
- dp[0][0] ：此時要想處于「買?」?fàn)顟B(tài)，必須把第?天的股票買了，因此 dp[0][0] = -prices[0] ；
- dp[0][1] ：啥也不用干即可，因此 dp[0][1] = 0 ；
- dp[0][2] ：?上沒有股票，買?下賣?下就處于冷凍期，此時收益為 0 ，因此 dp[0][2]= 0 。
??填表順序：
根據(jù)「狀態(tài)表示」，我們要三個表?起填，每?個表「從左往右」。
??返回值：
應(yīng)該返回「賣出狀態(tài)」下的最?值，因此應(yīng)該返回 max(dp[n - 1][1], dp[n - 1][2])
??代碼實現(xiàn)
class Solution {
public int maxProfit(int[] prices) {
int n = prices.length;
int[][] dp = new int[n][3];
dp[0][0] = - prices[0];
for(int i = 1; i < n; i++) {
dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] - prices[i]);
dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][2]);
dp[i][2] = dp[i - 1][0] + prices[i];
}
return Math.max(dp[n - 1][1], dp[n - 1][2]);
}
}
??買賣股票的最佳時期含手續(xù)費（medium）
??題目描述
給定一個整數(shù)數(shù)組 prices，其中 prices[i]表示第 i 天的股票價格 ；整數(shù) fee 代表了交易股票的手續(xù)費用。
你可以無限次地完成交易，但是你每筆交易都需要付手續(xù)費。如果你已經(jīng)購買了一個股票，在賣出它之前你就不能再繼續(xù)購買股票了。
返回獲得利潤的最大值。
注意：這里的一筆交易指買入持有并賣出股票的整個過程，每筆交易你只需要為支付一次手續(xù)費。
- 示例 1：
輸入：prices = [1, 3, 2, 8, 4, 9], fee = 2
輸出：8
解釋：能夠達(dá)到的最大利潤:
在此處買入 prices[0] = 1
在此處賣出 prices[3] = 8
在此處買入 prices[4] = 4
在此處賣出 prices[5] = 9
總利潤: ((8 - 1) - 2) + ((9 - 4) - 2) = 8 - 示例 2：
輸入：prices = [1,3,7,5,10,3], fee = 3
輸出：6
class Solution {
public int maxProfit(int[] prices, int fee) {
}
}
??算法思路
??狀態(tài)表示：
對于線性 dp ，我們可以?「經(jīng)驗 + 題?要求」來定義狀態(tài)表?：
- 以某個位置為結(jié)尾，進行操作；
- 以某個位置為起點，進行操作。
這里我們選擇比較常用的方式，以某個位置為結(jié)尾，結(jié)合題目要求，定義?個狀態(tài)表示：
由于有「買?」「可交易」兩個狀態(tài)，因此我們可以選擇用兩個數(shù)組，其中：
- f[i] 表示：第 i 天結(jié)束后，處于「買?」?fàn)顟B(tài)，此時的最大利潤；
- g[i] 表示：第 i 天結(jié)束后，處于「賣出」?fàn)顟B(tài)，此時的最大利潤。
??狀態(tài)轉(zhuǎn)移方程：
我們選擇在「賣出」的時候，支付這個手續(xù)費，那么在「買入」的時候，就不?再考慮?續(xù)費的問題。
對于 f[i] ，我們有兩種情況能到達(dá)這個狀態(tài)：
- 在 i - 1 天「持有」股票，第 i 天啥也不干。此時最?收益為 f[i - 1] ；
- 在 i - 1 天的時候「沒有」股票，在第 i 天買?股票。此時最?收益為 g[i - 1] - prices[i])
兩種情況下應(yīng)該取最大值，因此 f[i] = max(f[i - 1], g[i - 1] -prices[i]) 。
對于 g[i] ，我們也有兩種情況能夠到達(dá)這個狀態(tài)：
- 在 i - 1 天「持有」股票，但是在第 i 天將股票賣出。此時最大收益為： f[i - 1]+ prices[i] - fee) ，記得手續(xù)費；
- 在 i - 1 天「沒有」股票，然后第 i 天啥也不干。此時最大收益為： g[i - 1] ；
兩種情況下應(yīng)該取最大值，因此 g[i] = max(g[i - 1], f[i - 1] + prices[i] - free) 。
class Solution {
public int maxProfit(int[] prices, int fee) {
int[] f = new int[prices.length];
int[] g = new int[prices.length];
f[0] = -prices[0];
for (int i = 1; i < prices.length; i++) {
f[i] = Math.max(f[i - 1],g[i - 1] - prices[i]);
g[i] = Math.max(g[i - 1], f[i - 1] + prices[i] - fee);
}
return g[prices.length - 1];
}
}
??初始化：
由于需要用到前面的狀態(tài)，因此需要初始化第?個位置。
- 對于 f[0] ，此時處于「買入」?fàn)顟B(tài)，因此 f[0] = -prices[0] ；
- 對于 g[0] ，此時處于「沒有股票」?fàn)顟B(tài)，啥也不干即可獲得最大收益，因此 g[0] = 0
??填表順序：
毫?疑問是「從左往右」，但是兩個表需要?起填。
??返回值：
應(yīng)該返回「賣出」?fàn)顟B(tài)下，最后?天的最大值收益： g[n - 1]
??代碼實現(xiàn)
class Solution {
public int maxProfit(int[] prices, int fee) {
int[] f = new int[prices.length];
int[] g = new int[prices.length];
f[0] = -prices[0];
for (int i = 1; i < prices.length; i++) {
f[i] = Math.max(f[i - 1],g[i - 1] - prices[i]);
g[i] = Math.max(g[i - 1], f[i - 1] + prices[i] - fee);
}
return g[prices.length - 1];
}
}
??買賣股票的最佳時機 III
??題目描述
給定一個數(shù)組，它的第 i 個元素是一支給定的股票在第 i 天的價格。
設(shè)計一個算法來計算你所能獲取的最大利潤。你最多可以完成 兩筆 交易。
注意：你不能同時參與多筆交易（你必須在再次購買前出售掉之前的股票）。
- 示例 1:
輸入：prices = [3,3,5,0,0,3,1,4]
輸出：6
解釋：在第 4 天（股票價格 = 0）的時候買入，在第 6 天（股票價格 = 3）的時候賣出，這筆交易所能獲得利潤 = 3-0 = 3 。
隨后，在第 7 天（股票價格 = 1）的時候買入，在第 8 天 （股票價格 = 4）的時候賣出，這筆交易所能獲得利潤 = 4-1 = 3 。
-示例 2：
輸入：prices = [1,2,3,4,5]
輸出：4
解釋：在第 1 天（股票價格 = 1）的時候買入，在第 5 天 （股票價格 = 5）的時候賣出, 這筆交易所能獲得利潤 = 5-1 = 4 。
注意你不能在第 1 天和第 2 天接連購買股票，之后再將它們賣出。
因為這樣屬于同時參與了多筆交易，你必須在再次購買前出售掉之前的股票。 - 示例 3：
輸入：prices = [7,6,4,3,1]
輸出：0
解釋：在這個情況下, 沒有交易完成, 所以最大利潤為 0。 - 示例 4：
輸入：prices = [1]
輸出：0
class Solution {
public int maxProfit(int[] prices) {
}
}
??算法思路
??狀態(tài)表示：
對于線性 dp ，我們可以?「經(jīng)驗 + 題目要求」來定義狀態(tài)表示：
- 以某個位置為結(jié)尾，進行一系列操作；
- 以某個位置為起點，進行一系列操作。
這里我們選擇比較常?的?式，以某個位置為結(jié)尾，結(jié)合題目要求，定義?個狀態(tài)表?：
由于有「買?」「可交易」兩個狀態(tài)，因此我們可以選擇用兩個數(shù)組。但是這道題??還有交易次數(shù)的限制，因此我們還需要再加上?維，用來表示交易次數(shù)。其中：
-
f[i][j] 表?：第 i 天結(jié)束后，完成了 j 次交易，處于「買?」?fàn)顟B(tài)，此時的最?利潤；
-
g[i][j] 表?：第 i 天結(jié)束后，完成了 j 次交易，處于「賣出」?fàn)顟B(tài)，此時的最?利潤。
??狀態(tài)轉(zhuǎn)移方程：
對于 f[i][j] ，我們有兩種情況到這個狀態(tài)：
- 在 i - 1 天的時候，交易了 j 次，處于「買?」?fàn)顟B(tài)，第 i 天啥也不干即可。此時最大利潤為： f[i - 1][j] ；
- 在 i - 1 天的時候，交易了 j 次，處于「賣出」?fàn)顟B(tài)，第 i 天的時候把股票買了。此時的最?利潤為： g[i - 1][j] - prices[i] 。
綜上，我們要的是「最?利潤」，因此是兩者的最?值： f[i][j] = max(f[i - 1][j],g[i - 1][j] - prices[i]) 。
對于 g[i][j] ，我們也有兩種情況可以到達(dá)這個狀態(tài)：
- 在 i - 1 天的時候，交易了 j 次，處于「賣出」?fàn)顟B(tài)，第 i 天啥也不?即可。此時的最大利潤為： g[i - 1][j] ；
- 在 i - 1 天的時候，交易了 j - 1 次，處于「買?」?fàn)顟B(tài)，第 i 天把股票賣了，然后就完成了 j ?交易。此時的最?利潤為： f[i - 1][j - 1] + prices[i] 。但是這個狀態(tài)不?定存在，要先判斷?下。
綜上，我們要的是最?利潤，因此狀態(tài)轉(zhuǎn)移方程為：
g[i][j] = g[i - 1][j];
if(j >= 1) {
g[i][j] = max(g[i][j], f[i - 1][j - 1] + prices[i]);
}
??初始化：
由于需要用到 i = 0 時的狀態(tài)，因此我們初始化第?行即可。
- 當(dāng)處于第 0 天的時候，只能處于「買?過?次」的狀態(tài)，此時的收益為 -prices[0] ，因此 f[0][0] = - prices[0] 。
- 為了取 max 的時候，?些不存在的狀態(tài)「起不到干擾」的作用，我們統(tǒng)統(tǒng)將它們初始化為 - INF （用 INT_MIN 在計算過程中會有「溢出」的風(fēng)險，這? INF 折半取0x3f3f3f3f ，足夠小即可）
??填表順序：
從「上往下填」每?行，每?行「從左往右」，兩個表「?起填」。
??返回值：
返回處于「賣出狀態(tài)」的最?值，但是我們也「不知道是交易了?次」，因此返回 g 表最后?行的最大值。文章來源：http://www.zghlxwxcb.cn/news/detail-848844.html
??代碼實現(xiàn)
class Solution {
public int maxProfit(int[] prices) {
// 1. 創(chuàng)建 dp 表
// 2. 初始化
// 3. 填表
// 4. 返回值
int INF = 0x3f3f3f3f;
int n = prices.length;
int[][] f = new int[n][3];
int[][] g = new int[n][3];
for(int j = 0; j < 3; j++) {
f[0][j] = g[0][j] = -INF;
}
f[0][0] = -prices[0];
g[0][0] = 0;
for(int i = 1; i < n; i++) {
for (int j = 0; j < 3; j++) {
f[i][j] = Math.max(f[i - 1][j], g[i - 1][j] - prices[i]);
g[i][j] = g[i - 1][j];
// 判斷狀態(tài)是否存在
if (j - 1 >= 0) {
g[i][j] = Math.max(g[i][j], f[i - 1][j - 1] + prices[i]);
}
}
}
//找出最后一行的最大值
int ret = 0;
for(int j = 0; j < 3; j++) {
ret = Math.max(ret, g[n - 1][j]);
}
return ret;
}
}
?總結(jié)
關(guān)于《【算法優(yōu)選】 動態(tài)規(guī)劃之簡單多狀態(tài)dp問題——貳》就講解到這兒，感謝大家的支持，歡迎各位留言交流以及批評指正，如果文章對您有幫助或者覺得作者寫的還不錯可以點一下關(guān)注，點贊，收藏支持一下！文章來源地址http://www.zghlxwxcb.cn/news/detail-848844.html
到了這里，關(guān)于【算法優(yōu)選】 動態(tài)規(guī)劃之簡單多狀態(tài)dp問題——貳的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
