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

Unknown Unknown Unknown Unknown

无敌

回复 Buyringash 取消回复

Avatar placeholder

您的电子邮箱地址不会被公开。 必填项已用*标注