目錄
一.買賣股票的最佳時機:
二.買賣股票的最佳時機含冷凍期:
三.買賣股票的最佳時期含?續費:
四.買賣股票的最佳時機III:?
五.買賣股票的最佳時機IV:
買賣股票的最佳時機問題介紹:動態規劃買賣股票的最佳時機是一個經典的算法問題。該問題的目標是在給定的股票價格數組中,找到最大的利潤,即最佳的買入和賣出時間,使得買入時間早于賣出時間。
下面我們通過一些例題,來解決這一類動態規劃的問題:
一.買賣股票的最佳時機:
- 題目鏈接:121. 買賣股票的最佳時機 - 力扣(LeetCode)
- 題目描述:
給定一個數組?
prices
?,它的第?i
?個元素?prices[i]
?表示一支給定股票第?i
?天的價格。你只能選擇?某一天?買入這只股票,并選擇在?未來的某一個不同的日子?賣出該股票。設計一個算法來計算你所能獲取的最大利潤。
返回你可以從這筆交易中獲取的最大利潤。如果你不能獲取任何利潤,返回?
0
?。
①.動態規劃解法:
- 一.狀態表示dp[ i ][ j ]:下標為?
i
?這一天結束的時候,手上持股狀態為?j
?時,我們持有的最大利潤。這里我們定義狀態 j (兩種情況)分別為:- 0?買入狀態
- 1?可交易狀態
- 二.狀態轉移方程:
- dp[ i ][ 0 ] = Math.max( dp[ i - 1 ][ 0 ], -prices[ i ]) ; ①.在前面一天已經是買入狀態,今天選擇什么也不干,今天結束后,是買入狀態。②.前面是可交易狀態,今天選擇買入,則今天結束后是買入狀態,這里注意不是dp[ i - 1][ 1 ] - prices[ i ];因為只能交易一次,如果今天選擇買入,那后面一定要賣出(這算一次交易),此時才可能有最大利潤。則前面不能有交易,利潤為0.
- dp[ i ][ 1 ] = Math.max( dp[ i - 1][ 1 ],dp[ i - 1][ 0 ] + prices[ i ]);①.前面一天是可交易狀態,今天選擇什么也不干,今天結束后是可交易狀態。②.前面一天是買入狀態,今天選擇賣出,今天結束后是可交易狀態。
- 三.初始化:根據狀態表示:
- dp[ 0 ][ 0 ] = - prices[ 0 ];第一天選擇買入,此時利潤為 - prices[ 0 ]
- dp[ 0 ][ 1 ] = 0;第一天選擇什么也不干或則交易一次,此時的利潤為0;
- 四.填表順序:根據狀態轉移方程,從左往右,從上往下填寫.
- 五.返回值:dp[ n - 1 ][ 1 ];n為prices數組的長度,最后一天結束后,是可交易狀態,此時為最大利潤.
各個狀態關系圖:
代碼詳解:
class Solution {// 1. 創建 dp 表// 2. 初始化// 3. 填表// 4. 返回值public int maxProfit(int[] prices) {int n = prices.length;int[][] dp = new int[n][2];//初始化dp[0][0] = -prices[0];dp[0][1] = 0;for(int i = 1;i < n;i++){//注意這里不是dp[i - 1][1] - prices[i];dp[i][0] = Math.max(dp[i - 1][0], - prices[i]);dp[i][1] = Math.max(dp[i - 1][1],dp[i - 1][0] + prices[i]);}//返回值return dp[n - 1][1];} }
②.暴力解法(相對簡單這里給出解題過程):?
代碼詳解:
class Solution {public int maxProfit(int[] prices) {int cost = Integer.MAX_VALUE;int profit = 0;for(int price : prices){cost = Math.min(cost,price);profit = Math.max(profit,price - cost);}return profit;}
}
運行結果:
?
二.買賣股票的最佳時機含冷凍期:
- 題目鏈接:309. 買賣股票的最佳時機含冷凍期 - 力扣(LeetCode)
- 問題描述:
給定一個整數數組
prices
,其中第??prices[i]
?表示第?i
?天的股票價格 。?設計一個算法計算出最大利潤。在滿足以下約束條件下,你可以盡可能地完成更多的交易(多次買賣一支股票):
-
賣出股票后,你無法在第二天買入股票 (即冷凍期為 1 天)。
-
注意:你不能同時參與多筆交易(你必須在再次購買前出售掉之前的股票)。
動態規劃解法:
一.狀態表示:dp[ i ][ j ]:由于有「買?」「可交易」「冷凍期」三個狀態,因此我們可以選擇?三個數組,其中:
- dp[i][0] 表?:第 i 天結束后,處于「買?」狀態,此時的最?利潤;
- dp[i][1] 表?:第 i 天結束后,處于「可交易」狀態,此時的最?利潤;
- dp[i][2] 表?:第 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][2]); ①.前面一天是可交易狀態,今天啥也不干,今天結束后是可交易狀態②.前面一天是冷凍期,今天啥也不干,今天過后是可交易狀態
- dp[i][2] = dp[i - 1][0] + prices[i];前面一天是買入狀態,今天選擇賣出,今天過后是冷凍期
三.初始化:
dp[0][0] = - prices[0] ;? ?dp[0][1] = 0 ;? ? dp[0][2] = 0;
四.填表順序:從左往右,從上往下,依次填寫三個表
五.返回值:狀態轉移方程三者的最大值:
?max(dp[n - 1][1], dp[n - 1] [2]);dp[n - 1][0]不可能是最大值,這里不用考慮進去(如果考慮進去了也沒關系)
各個狀態關系圖:
代碼詳解:
class Solution {// 1. 創建 dp 表// 2. 初始化// 3. 填表// 4. 返回值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]);} }
運行結果:?
三.買賣股票的最佳時期含?續費:
題目鏈接:714. 買賣股票的最佳時機含手續費 - 力扣(LeetCode)
題目描述:
給定一個整數數組?prices
,其中?prices[i]
表示第?i
?天的股票價格 ;整數?fee
?代表了交易股票的手續費用。
你可以無限次地完成交易,但是你每筆交易都需要付手續費。如果你已經購買了一個股票,在賣出它之前你就不能再繼續購買股票了。
返回獲得利潤的最大值。
注意:這里的一筆交易指買入持有并賣出股票的整個過程,每筆交易你只需要為支付一次手續費。
?動態規劃解法:
一.狀態表示:由于有「買?」「可交易」兩個狀態,因此我們可以選擇?兩個數組來定義我們的狀態(或則一個二維數組也行),其中:
- f[i] 表?:第 i 天結束后,處于「買?」狀態,此時的最?利潤;
- g[i] 表?:第 i 天結束后,處于「賣出」狀態,此時的最?利潤.
二.狀態轉移方程 :我們選擇在「賣出」的時候,?付這個?續費,那么在「買?」的時候,就不?再考慮?續費的問題(完成一次交易支付手續費):
- f[i] = max(f[i - 1], g[i - 1] - prices[i]) ;①.在 i - 1 天「持有」股票,第 i 天啥也不?。此時最?收益為 f[i - 1] ;②.在 i - 1 天的時候「沒有」股票,在第 i 天買?股票。此時最?收益為 g[i - 1] - prices[i]) ;
- g[i] = max(g[i - 1], f[i - 1] + prices[i] - fee);①.在 i - 1 天「持有」股票,但是在第 i 天將股票賣出。此時最?收益為: f[i - 1] + prices[i] - fee) ,記得?續費;②.在 i - 1 天「沒有」股票,然后第 i 天啥也不?。此時最?收益為: g[i - 1]
三.初始化:由于需要?到前?的狀態,因此需要初始化第?個位置:
- 對于 f[0] ,此時處于「買?」狀態,因此 f[0] = -prices[0]
- 對于 g[0] ,此時處于「沒有股票」狀態,啥也不?即可獲得最?收益,因此 g[0] = 0?
四.填表順序:從左到右兩個表一起填
五.返回值:應該返回「賣出」狀態下,最后?天的最?值收益: g[n - 1]?
代碼詳解:
class Solution {public int maxProfit(int[] prices, int fee) {int n = prices.length;int[] f = new int[n];int[] g = new int[n];f[0] = -prices[0];for(int i = 1;i < n;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 Math.max(f[n - 1],g[n - 1]);} }
運行結果:
四.買賣股票的最佳時機III:?
題目鏈接:123. 買賣股票的最佳時機 III - 力扣(LeetCode)
題目描述:
給定一個數組,它的第?i
?個元素是一支給定的股票在第?i
?天的價格。
設計一個算法來計算你所能獲取的最大利潤。你最多可以完成?兩筆?交易。
注意:你不能同時參與多筆交易(你必須在再次購買前出售掉之前的股票)。
動態規劃解法:
一.狀態表示:由于有「買?」「可交易」兩個狀態,因此我們可以選擇?兩個數組。但是這道題??還有交易次 數的限制,因此我們還需要再加上?維,?來表?交易次數。其中:
- f[i][j] 表?:第 i 天結束后,完成了 j 次交易,處于「買?」狀態,此時的最?利 潤;
- g[i][j] 表?:第 i 天結束后,完成了 j 次交易,處于「賣出」狀態,此時的最?利 潤。
二.狀態轉移方程:
- f[i][j] = max(f[i - 1][j], g[i - 1][j] - prices[i]);①.在 i - 1 天的時候,交易了 j 次,處于「買?」狀態,第 i 天啥也不?即可。此時最 ?利潤為: f[i - 1][j] ;②.在 i - 1 天的時候,交易了 j 次,處于「賣出」狀態,第 i 天的時候把股票買了。此 時的最?利潤為: g[i - 1][j] - prices[i] 。
- g[i][j] = g[i - 1][j];
? ? ? if(j >?0) g[i][j] = max(g[i][j], f[i - 1][j - 1] + prices[i]);??
? ? ?①.在 i - 1 天的時候,交易了 j 次,處于「賣出」狀態,第 i 天啥也不?即可。此時的 最? ? ? ? ? ? ??利潤為: g[i - 1][j] ;
? ? ②.在 i - 1 天的時候,交易了 j - 1 次,處于「買?」狀態,第 i 天把股票賣了,然 后就完? ? ? ? ? 成了 j ?交易。此時的最?利潤為: f[i - 1][j - 1] + prices[i] 。但 是這個狀態不?定存? ? ? ? ? ? ? 在,要先判斷?下。
三.初始化:
- 當處于第 0 天的時候,只能處于「買?過?次」的狀態,此時的收益為 -prices[0] ,因 此 f[0][0] = - prices[0] 。
- 為了取 max 的時候,?些不存在的狀態「起不到?擾」的作?,我們統統將它們初始化為 - INF (? INT_MIN 在計算過程中會有「溢出」的?險,這? INF 折半取 0x3f3f3f3f ,?夠?即可)
四.填表順序:從「上往下填」每??,每??「從左往右」,兩個表「?起填」。
五.返回值:返回處于「賣出狀態」的最?值,但是我們也「不知道是交易了?次」,因此返回 g 表最后?? 的最?值。
代碼詳解:
class Solution {static int INF = -0x3f3f3f3f;public int maxProfit(int[] prices) {int n = prices.length;int[][] f = new int[n][3];int[][] g = new int[n][3];//1.f[0][0] = -prices[0];for(int i = 1;i < f[0].length;i++){f[0][i] = INF;}for(int j = 1;j < g[0].length;j++){g[0][j] = INF;//Integer.MIN_VALUE/2}//2.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];if(j > 0){g[i][j] = Math.max(g[i][j],f[i - 1][j - 1] + prices[i]);}}}int res = Integer.MIN_VALUE;for(int j = 0;j < 3;j++){ res = Math.max(res,g[n - 1][j]);}return res;} }
運行結果:
五.買賣股票的最佳時機IV:
題目鏈接:188. 買賣股票的最佳時機 IV - 力扣(LeetCode)
題目描述:
給你一個整數數組?prices
?和一個整數?k
?,其中?prices[i]
?是某支給定的股票在第?i
?天的價格。
設計一個算法來計算你所能獲取的最大利潤。你最多可以完成?k
?筆交易。也就是說,你最多可以買?k
?次,賣?k
?次。
注意:你不能同時參與多筆交易(你必須在再次購買前出售掉之前的股票)。
動態規劃解法:
一.狀態表示:為了更加清晰的區分「買?」和「賣出」,我們換成「有股票」和「?股票」兩個狀態:
- f[i][j] 表?:第 i 天結束后,完成了 j 筆交易,此時處于「有股票」狀態的最?收益;
- g[i][j] 表?:第 i 天結束后,完成了 j 筆交易,此時處于「?股票」狀態的最?收益
二.狀態轉移方程:
- f[i][j] = max(f[i - 1][j], g[i - 1][j] - prices[i]);①.在 i - 1 天的時候,??「有股票」,并且交易了 j 次。在第 i 天的時候,啥也不?。 此時的收益為 f[i - 1][j] ;②.在 i - 1 天的時候,??「沒有股票」,并且交易了 j 次。在第 i 天的時候,買了股 票。那么 i 天結束之后,我們就有股票了。此時的收益為 g[i - 1][j] - prices[i];
- g[i][j] = max(g[i - 1][j], f[i - 1][j - 1] + prices[i]);①.在 i - 1 天的時候,??「沒有股票」,并且交易了 j 次。在第 i 天的時候,啥也不 ?。此時的收益為 g[i - 1][j] ;②.在 i - 1 天的時候,??「有股票」,并且交易了 j - 1 次。在第 i 天的時候,把 股票賣了。那么 i 天結束之后,我們就交易了 j 次。此時的收益為 f[i - 1][j - 1] + prices[i] ;
三.初始化:
- 當處于第 0 天的時候,只能處于「買?過?次」的狀態,此時的收益為 -prices[0] ,因 此 f[0][0] = - prices[0]
- 為了取 max 的時候,?些不存在的狀態「起不到?擾」的作?,我們統統將它們初始化為 - INF (? INT_MIN 在計算過程中會有「溢出」的?險,這? INF 折半取 0x3f3f3f3f ,?夠?即可)
四.填表順序:從上往下填每??,每??從左往右,兩個表?起填。
五.返回值:返回處于賣出狀態的最?值,但是我們也不知道是交易了?次,因此返回 g 表最后??的最? 值
代碼詳解:
class Solution {static int INF = -0x3f3f3f3f;public int maxProfit(int k, int[] prices) {int n = prices.length;int[][] f = new int[n][k + 1];int[][] g = new int[n][k + 1];//1.f[0][0] = -prices[0];for(int i = 1;i < f[0].length;i++){f[0][i] = INF;//->防止越界g[i - 1][j] - prices[i];}for(int j = 1;j < g[0].length;j++){g[0][j] = INF;//Integer.MIN_VALUE/2}//2.for(int i = 1;i < n;i++){for(int j = 0;j < k + 1;j++){f[i][j] = Math.max(f[i - 1][j],g[i - 1][j] - prices[i]);g[i][j] = g[i - 1][j];if(j > 0){g[i][j] = Math.max(g[i][j],f[i - 1][j - 1] + prices[i]);}}}int res = Integer.MIN_VALUE;for(int j = 0;j < k + 1;j++){ res = Math.max(res,g[n - 1][j]);}return res;} }
運行結果:
?結語:?寫博客不僅僅是為了分享學習經歷,同時這也有利于我鞏固知識點,總結該知識點,由于作者水平有限,對文章有任何問題的還請指出,接受大家的批評,讓我改進。同時也希望讀者們不吝嗇你們的點贊+收藏+關注,你們的鼓勵是我創作的最大動力!