121. Best Time to Buy and Sell Stock
https://leetcode.com/problems/best-time-to-buy-and-sell-stock/description/
使用动态规划“局部最优和全局最优”解法。
代码如下：
class Solution:
def maxProfit(self, prices):
"""
:type prices: List[int]
:rtype: int
"""
if not prices or len(prices) == 0:
return 0
local_max = global_max = 0
for i in range(len(prices) - 1):
local_max = max(0, local_max) + prices[i + 1] - prices[i]
global_max = max(local_max, global_max)
return global_max
122. Best Time to Buy and Sell Stock II
https://leetcode.com/problems/best-time-to-buy-and-sell-stock-ii/description/
这道题并不是动态规划题目，放在这只是把股票问题补全。
思路很简单，因为可以做无数次的交易，所以只要赚钱的都加上即可。
代码如下：
class Solution:
def maxProfit(self, prices):
"""
:type prices: List[int]
:rtype: int
"""
if not prices or len(prices) == 0:
return 0
res = 0
for i in range(len(prices) - 1):
if prices[i + 1] - prices[i] > 0:
res += prices[i + 1] - prices[i]
return res
123. Best Time to Buy and Sell Stock III
https://leetcode.com/problems/best-time-to-buy-and-sell-stock-iii/description/
使用通用的K次解法，但较难理解。
代码如下：
class Solution:
def maxProfit(self, prices):
"""
:type prices: List[int]
:rtype: int
"""
if not prices or len(prices) == 0:
return 0
local_max = [0] * 3
global_max = [0] * 3
for i in range(len(prices) - 1):
diff = prices[i + 1] - prices[i]
for j in range(1, 3)[::-1]:
local_max[j] = max(global_max[j - 1] + max(0, diff), local_max[j] + diff)
global_max[j] = max(global_max[j], local_max[j])
return global_max[2]
188. Best Time to Buy and Sell Stock IV
https://leetcode.com/problems/best-time-to-buy-and-sell-stock-iv/description/
上道题是k=2的特殊情况，这道题直接用k即可。
注意，如果k比数组长度还大，相当于变成可以有无限交易次数的#122题，可以简化时间复杂度。
代码如下：
class Solution:
def maxProfit(self, k, prices):
"""
:type k: int
:type prices: List[int]
:rtype: int
"""
if k == 0 or not prices or len(prices) == 0:
return 0
if k >= len(prices):
return self.getMaxProfit(prices)
local_max = [0] * (k + 1)
global_max = [0] * (k + 1)
for i in range(len(prices) - 1):
diff = prices[i + 1] - prices[i]
for j in range(1, k + 1)[::-1]:
local_max[j] = max(global_max[j - 1] + max(0, diff), local_max[j] + diff)
global_max[j] = max(global_max[j], local_max[j])
return global_max[-1]
def getMaxProfit(self, prices):
res = 0
for i in range(len(prices) - 1):
diff = prices[i + 1] - prices[i]
res += max(0, diff)
return res
309. Best Time to Buy and Sell Stock with Cooldown
https://leetcode.com/problems/best-time-to-buy-and-sell-stock-with-cooldown/description/
首先，画出状态机，类似下链接：
Share my DP solution (By State Machine Thinking)
然后，根据状态机写出递推式，进行计算即可，可参照下链接：
4-line Python solution, 52 ms
代码如下：
class Solution:
def maxProfit(self, prices):
"""
:type prices: List[int]
:rtype: int
"""
can_buy, hold, after_sold = 0, float('-inf'), float('-inf')
for price in prices:
can_buy, hold, after_sold = max(can_buy, after_sold), max(hold, can_buy - price), hold + price
return max(can_buy, after_sold)
714. Best Time to Buy and Sell Stock with Transaction Fee
https://leetcode.com/problems/best-time-to-buy-and-sell-stock-with-transaction-fee/description/
dp[i][0]: 第i天, 手里没有股票.
dp[i][1]: 第i天, 手里有股票.
dp[i][1] = max(dp[i-1][0] - nums[i], dp[i-1][1]): 在i-1天没有，并在第i天买股票；或者在i-1天有股票，第i天什么也不做.
dp[i][0] = max(dp[i-1][1] + nums[i] - fee, dp[i-1][0]): 在i-1天有股票，并在第i天卖出去；或者在i-1天就没有股票，第i天什么也不做.
代码如下：
class Solution:
def maxProfit(self, prices, fee):
"""
:type prices: List[int]
:type fee: int
:rtype: int
"""
if not prices or len(prices) <= 1:
return 0
dp = [[0, 0] for x in range(len(prices))]
dp[0][0], dp[0][1] = 0, -prices[0]
for i in range(1, len(prices)):
dp[i][0] = max(dp[i - 1][1] + prices[i] - fee, dp[i - 1][0])
dp[i][1] = max(dp[i - 1][0] - prices[i], dp[i - 1][1])
return dp[-1][0]
网友评论