121. 買(mǎi)賣股票的最佳時(shí)機(jī)
題目描述
給定一個(gè)數(shù)組腐缤，它的第 i 個(gè)元素是一支給定股票第 i 天的價(jià)格舞蔽。
如果你最多只允許完成一筆交易（即買(mǎi)入和賣出一支股票一次）婉徘，設(shè)計(jì)一個(gè)算法來(lái)計(jì)算你所能獲取的最大利潤(rùn)钻趋。
注意：你不能在買(mǎi)入股票前賣出股票邻寿。
示例 1:
輸入: [7,1,5,3,6,4]
輸出: 5
解釋: 在第 2 天（股票價(jià)格 = 1）的時(shí)候買(mǎi)入渤弛，在第 5 天（股票價(jià)格 = 6）的時(shí)候賣出己肮，最大利潤(rùn) = 6-1 = 5 主穗。
注意利潤(rùn)不能是 7-1 = 6, 因?yàn)橘u出價(jià)格需要大于買(mǎi)入價(jià)格圃伶；同時(shí)堤如，你不能在買(mǎi)入前賣出股票。
示例 2:
輸入: [7,6,4,3,1]
輸出: 0
解釋: 在這種情況下, 沒(méi)有交易完成, 所以最大利潤(rùn)為 0窒朋。
Related Topics 數(shù)組 動(dòng)態(tài)規(guī)劃
由于最多只交易一次搀罢，我們只需要找到當(dāng)前天以前的股票最低價(jià)，也就能計(jì)算出當(dāng)前天的最大利潤(rùn)侥猩。
class Solution:
def maxProfit(self, prices: List[int]) -> int:
n = len(prices)
if n <= 1:
return 0
low = prices[0]
profit = 0
for i in range(1, n):
low = min(low, prices[i])
profit = max(profit, prices[i] - low)
return profit
下面我們嘗試?yán)脛?dòng)態(tài)規(guī)劃算法進(jìn)行求解榔至。
分析思路：
動(dòng)態(tài)規(guī)劃也就是窮舉狀態(tài)。對(duì)于每一天來(lái)說(shuō)欺劳，我們有以下3種選擇：不交易唧取、買(mǎi)入、賣出划提。但是這3種狀態(tài)并不是自由選擇的枫弟，買(mǎi)入需要在賣出以后(第一次買(mǎi)入除外)，賣出需要在買(mǎi)入以后鹏往。另外還需要考慮交易次數(shù)的限制淡诗。所以綜合起來(lái)，我們的狀態(tài)有3類：天數(shù)掸犬、交易次數(shù)袜漩、持股狀態(tài)。
所以我們可以定義狀態(tài)數(shù)組為 dp[i][j][k]湾碎，表示第 i 天最多交易 j 次且持股狀態(tài)為 k{0,1} 的狀態(tài)下能獲得的最大利潤(rùn)宙攻，其中 k=0 表示不持股，k=1表示持股介褥。
dp[i][j][0]如何轉(zhuǎn)移座掘？
若不交易，則dp[i][j][0] = dp[i-1][j][0]
賣出后的不持股柔滔，則dp[i][j][0] = dp[i-1][j][1]+prices[i]
所以dp[i][j][0] = max( dp[i-1][j][0], dp[i-1][j][1]+prices[i])dp[i][j][1]如何轉(zhuǎn)移溢陪？
若不交易，則dp[i][j][1] = dp[i-1][j][1]
買(mǎi)入后的持股睛廊，則dp[i][j][1] = dp[i-1][j][0]-prices[i]
所以dp[i][j][1] = max( dp[i-1][j][1], dp[i-1][j-1][0]-prices[i])base case
第 0 天不持股形真，最大利潤(rùn)為0
dp[0][j][0] = 0
第 0 天持股，最大利潤(rùn)為-prices[0]
dp[0][j][1] = -prices[0]
交易次數(shù)為 0超全，不持股狀態(tài)下利潤(rùn)為0咆霜，不可能為持股狀態(tài)邓馒，故設(shè)置為負(fù)無(wú)窮。
dp[i][0][0] = 0
dp[i][0][1] = float('-inf')輸出
即第n-1天最大交易次數(shù)下且不持股狀態(tài)下的最大利潤(rùn)蛾坯。
有了這套思路光酣，對(duì)于買(mǎi)賣股票類問(wèn)題，我們均可以套用脉课。
回到題目救军，由于最多交易一次，即 j=1倘零，此時(shí)狀態(tài)轉(zhuǎn)移方程為：
由于交易次數(shù)這個(gè)維度均為1唱遭，所以可以省略，最后的狀態(tài)轉(zhuǎn)移方程為：
class Solution:
def maxProfit(self, prices: List[int]) -> int:
n = len(prices)
if n <= 1:
return 0
dp = [[0, 0] for _ in range(n)]
# 初始化
dp[0][0] = 0
dp[0][1] = -prices[0]
# 遍歷狀態(tài)
for i in range(1, n):
dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i])
dp[i][1] = max(dp[i-1][1], -prices[i])
# print(dp)
return dp[n-1][0]
由于 dp[i] 只與 dp[i-1] 有關(guān)呈驶，進(jìn)行狀態(tài)壓縮：
class Solution:
def maxProfit(self, prices: List[int]) -> int:
n = len(prices)
if n <= 1:
return 0
sale = 0
buy = -prices[0]
for i in range(1, n):
sale = max(sale, buy + prices[i])
buy = max(buy, -prices[i])
return sale
122. 買(mǎi)賣股票的最佳時(shí)機(jī) II
題目描述
給定一個(gè)數(shù)組胆萧，它的第 i 個(gè)元素是一支給定股票第 i 天的價(jià)格。
設(shè)計(jì)一個(gè)算法來(lái)計(jì)算你所能獲取的最大利潤(rùn)俐东。你可以盡可能地完成更多的交易（多次買(mǎi)賣一支股票）跌穗。
注意：你不能同時(shí)參與多筆交易（你必須在再次購(gòu)買(mǎi)前出售掉之前的股票）。
示例 1:
輸入: [7,1,5,3,6,4]
輸出: 7
解釋: 在第 2 天（股票價(jià)格 = 1）的時(shí)候買(mǎi)入虏辫，在第 3 天（股票價(jià)格 = 5）的時(shí)候賣出, 這筆交易所能獲得利潤(rùn) = 5-1 = 4 蚌吸。
隨后，在第 4 天（股票價(jià)格 = 3）的時(shí)候買(mǎi)入砌庄，在第 5 天（股票價(jià)格 = 6）的時(shí)候賣出, 這筆交易所能獲得利潤(rùn) = 6-3 = 3 羹唠。
示例 2:
輸入: [1,2,3,4,5]
輸出: 4
解釋: 在第 1 天（股票價(jià)格 = 1）的時(shí)候買(mǎi)入，在第 5 天 （股票價(jià)格 = 5）的時(shí)候賣出, 這筆交易所能獲得利潤(rùn) = 5-1 = 4 娄昆。
注意你不能在第 1 天和第 2 天接連購(gòu)買(mǎi)股票佩微，之后再將它們賣出。
因?yàn)檫@樣屬于同時(shí)參與了多筆交易萌焰，你必須在再次購(gòu)買(mǎi)前出售掉之前的股票哺眯。
示例 3:
輸入: [7,6,4,3,1]
輸出: 0
解釋: 在這種情況下, 沒(méi)有交易完成, 所以最大利潤(rùn)為 0。
提示：
1 <= prices.length <= 3 * 10 ^ 4
0 <= prices[i] <= 10 ^ 4
Related Topics 貪心算法 數(shù)組
此題與上一題的不同之處在于交易次數(shù)無(wú)限制扒俯。還是套用我們上面的分析思路奶卓，狀態(tài)轉(zhuǎn)移方程為
交易次數(shù)無(wú)限制，我們也可以理解為 j=+infinity撼玄，此時(shí) j-1 和 j 可以認(rèn)為相等夺姑，即第二維同樣可以省略，所以狀態(tài)轉(zhuǎn)移方程可寫(xiě)成：
class Solution:
def maxProfit(self, prices: List[int]) -> int:
# dp[i][k] 表示第i天持股狀態(tài)為k{0: 不持股, 1: 持股}的最大利潤(rùn)
n = len(prices)
if n <= 1:
return 0
dp = [[0, 0] for _ in range(n)]
dp[0][1] = -prices[0]
for i in range(1, n):
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])
# print(dp)
return dp[n-1][0]
同樣進(jìn)行進(jìn)行狀態(tài)壓縮：
class Solution:
def maxProfit(self, prices: List[int]) -> int:
# dp[i][k] 表示第i天持股狀態(tài)為k{0: 不持股, 1: 持股}的最大利潤(rùn)
n = len(prices)
if n <= 1:
return 0
sale = 0
buy = -prices[0]
for i in range(1, n):
sale = max(sale, buy+prices[i])
buy = max(buy, sale-prices[i])
return sale
123. 買(mǎi)賣股票的最佳時(shí)機(jī) III
題目描述
給定一個(gè)數(shù)組掌猛，它的第 i 個(gè)元素是一支給定的股票在第 i 天的價(jià)格盏浙。
設(shè)計(jì)一個(gè)算法來(lái)計(jì)算你所能獲取的最大利潤(rùn)。你最多可以完成 兩筆 交易。
注意: 你不能同時(shí)參與多筆交易（你必須在再次購(gòu)買(mǎi)前出售掉之前的股票）废膘。
示例 1:
輸入: [3,3,5,0,0,3,1,4]
輸出: 6
解釋: 在第 4 天（股票價(jià)格 = 0）的時(shí)候買(mǎi)入辣往，在第 6 天（股票價(jià)格 = 3）的時(shí)候賣出，這筆交易所能獲得利潤(rùn) = 3-0 = 3 殖卑。
隨后，在第 7 天（股票價(jià)格 = 1）的時(shí)候買(mǎi)入坊萝，在第 8 天 （股票價(jià)格 = 4）的時(shí)候賣出孵稽，這筆交易所能獲得利潤(rùn) = 4-1 = 3 。
示例 2:
輸入: [1,2,3,4,5]
輸出: 4
解釋: 在第 1 天（股票價(jià)格 = 1）的時(shí)候買(mǎi)入十偶，在第 5 天 （股票價(jià)格 = 5）的時(shí)候賣出, 這筆交易所能獲得利潤(rùn) = 5-1 = 4 菩鲜。
注意你不能在第 1 天和第 2 天接連購(gòu)買(mǎi)股票，之后再將它們賣出惦积。
因?yàn)檫@樣屬于同時(shí)參與了多筆交易接校，你必須在再次購(gòu)買(mǎi)前出售掉之前的股票。
示例 3:
輸入: [7,6,4,3,1]
輸出: 0
解釋: 在這個(gè)情況下, 沒(méi)有交易完成, 所以最大利潤(rùn)為 0狮崩。
Related Topics 數(shù)組 動(dòng)態(tài)規(guī)劃
現(xiàn)在交易次數(shù)被限制為 k=2蛛勉，我們可以列舉第二維的狀態(tài)：
class Solution:
def maxProfit(self, prices: List[int]) -> int:
n = len(prices)
if n <= 1:
return 0
dp = [[[0, 0] for _ in range(3)] for _ in range(n)]
# 初始化
dp[0][0][1] = float('-inf')
dp[0][1][1] = -prices[0]
dp[0][2][1] = -prices[0]
for i in range(1, n):
# dp[i][0][0] = 0
# dp[i][0][1] = float('-inf')
dp[i][1][0] = max(dp[i-1][1][0], dp[i-1][1][1]+prices[i])
dp[i][1][1] = max(dp[i-1][1][1], -prices[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][1][0]-prices[i])
return dp[n-1][2][0]
同樣進(jìn)行狀態(tài)壓縮：
class Solution:
def maxProfit(self, prices: List[int]) -> int:
n = len(prices)
if n <= 1:
return 0
first_buy = -prices[0]
first_sale = float('-inf')
second_buy = float('-inf')
second_sale = float('-inf')
for i in range(1, n):
first_buy = max(first_buy, -prices[i])
first_sale = max(first_sale, first_buy+prices[i])
second_buy = max(second_buy, first_sale-prices[i])
second_sale = max(second_sale, second_buy+prices[i])
return second_sale
188. 買(mǎi)賣股票的最佳時(shí)機(jī) IV
題目要求最多交易次數(shù)為k，針對(duì)前面幾題的分析睦柴，我們可以對(duì)k進(jìn)行分段討論诽凌。
309. 最佳買(mǎi)賣股票時(shí)機(jī)含冷凍期
題目描述
給定一個(gè)整數(shù)數(shù)組，其中第 i 個(gè)元素代表了第 i 天的股票價(jià)格 坦敌。
設(shè)計(jì)一個(gè)算法計(jì)算出最大利潤(rùn)侣诵。在滿足以下約束條件下，你可以盡可能地完成更多的交易（多次買(mǎi)賣一支股票）:
你不能同時(shí)參與多筆交易（你必須在再次購(gòu)買(mǎi)前出售掉之前的股票）狱窘。
賣出股票后杜顺，你無(wú)法在第二天買(mǎi)入股票 (即冷凍期為 1 天)。
示例:
輸入: [1,2,3,0,2]
輸出: 3
解釋: 對(duì)應(yīng)的交易狀態(tài)為: [買(mǎi)入, 賣出, 冷凍期, 買(mǎi)入, 賣出]
Related Topics 動(dòng)態(tài)規(guī)劃
還是套用前面的思路
class Solution:
def maxProfit(self, prices: List[int]) -> int:
n = len(prices)
if n <= 1:
return 0
dp = [[0, 0] for _ in range(n)]
# 初始化
dp[0][1] = -prices[0]
for i in range(1, n):
dp[i][0] = max(dp[i-1][0], dp[i-1][1]+prices[i])
if i == 1:
dp[i][1] = max(dp[i-1][1], -prices[i])
else:
dp[i][1] = max(dp[i-1][1], dp[i-2][0]-prices[i])
return dp[n-1][0]
714. 買(mǎi)賣股票的最佳時(shí)機(jī)含手續(xù)費(fèi)
參考
- labuladong 的解題蘸炸。(放鏈接一直被吞)
