https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-iii/
# -*- coding:utf-8 -*-
"""
┏┛ ┻━━━━━┛ ┻┓
┃ ┃
┃ ━ ┃
┃ ┳┛ ┗┳ ┃
┃ ┃
┃ ┻ ┃
┃ ┃
┗━┓ ┏━━━┛
┃ ┃ 神兽保佑
┃ ┃ 代码无BUG!
┃ ┗━━━━━━━━━┓
┃ ┣┓
┃ ┏┛
┗━┓ ┓ ┏━━━┳ ┓ ┏━┛
┃ ┫ ┫ ┃ ┫ ┫
┗━┻━┛ ┗━┻━┛
"""
class Solution(object):
def maxProfit(self, prices):
"""
:type prices: List[int]
:rtype: int
"""
if prices == []:
return 0
length = len(prices)
# 结束时的最高利润=[天数][是否持有股票][卖出次数]
dp = [[[0, 0, 0], [0, 0, 0]] for i in range(0, length)]
# 第一天休息
dp[0][0][0] = 0
# 第一天买入
dp[0][1][0] = -prices[0]
# 第一天不可能已经有卖出
dp[0][0][1] = float('-inf')
dp[0][0][2] = float('-inf')
# 第一天不可能已经卖出
dp[0][1][1] = float('-inf')
dp[0][1][2] = float('-inf')
for i in range(1, length):
# 未持股,未卖出过,说明从未进行过买卖
dp[i][0][0] = 0
# 未持股,卖出过1次,可能是今天卖的,可能是之前卖的
dp[i][0][1] = max(dp[i - 1][1][0] + prices[i], dp[i - 1][0][1])
# 未持股,卖出过2次,可能是今天卖的,可能是之前卖的
dp[i][0][2] = max(dp[i - 1][1][1] + prices[i], dp[i - 1][0][2])
# 持股,未卖出过,可能是今天买的,可能是之前买的
dp[i][1][0] = max(dp[i - 1][0][0] - prices[i], dp[i - 1][1][0])
# 持股,卖出过1次,可能是今天买的,可能是之前买的
dp[i][1][1] = max(dp[i - 1][0][1] - prices[i], dp[i - 1][1][1])
# 持股,卖出过2次,不可能
dp[i][1][2] = float('-inf')
return max(dp[length - 1][0][1], dp[length - 1][0][2], 0)
if __name__ == '__main__':
prices = [3, 3, 5, 0, 0, 3, 1, 4]
print(Solution().maxProfit(prices))
思路:开始有点自闭了,好难啊emm。
这个刚开始肯定是确实动态规划的,就是状态太难找了,尝试过三维数组打状态失败了(确实可以用三维数组打状态,但是我太菜了,没捣腾出来)。然后就是上面这个方法。
唉,学无止境。
1 条评论
Buyringash · 2020-04-27 10:20
无敌