心路历程这道题的建模和股票问题一样只不过需要在状态上增加一个处于冻结期状态1第i天2第i天持有股票的状态持有不持有被冻结不持有未被冻结动作买入、卖出、不操作返回值当前状态下的收益注意的点1、注意思考清楚所有的状态转移情况当第i天处于持有状态时第i-1天可能有两个状态不持有不冻结or持有;2、最后一天一定是手里不持有收益最大所以是max(dp(n-1, 0), dp(n-1, 1))而不是max(dp(n-1, 0), dp(n-1, 1), dp(n-1, 2)).解法动态规划DP数组classSolution:defmaxProfit(self,prices:List[int])-int:nlen(prices)ifn0:return0dp[[0,0,0]for_inrange(n)]# 持有不持有冻结不持有不冻结dp[0][0]-prices[0]# 状态转移受限foriinrange(1,n):dp[i][0]max(dp[i-1][0],dp[i-1][2]-prices[i])dp[i][1]dp[i-1][0]prices[i]dp[i][2]max(dp[i-1][1],dp[i-1][2])returnmax(dp[n-1][0],dp[n-1][1],dp[n-1][2])递归classSolution:defmaxProfit(self,prices:List[int])-int:cachedefdp(i,j):# j 0 1 2 : 不持有不冻结 不持有冻结 持有ifi0andj0:return0elifi0andj1:return0elifi0andj2:return-prices[0]# 假设从-1时刻转移过来那就是买了0位置的股票ifj0:returnmax(dp(i-1,0),dp(i-1,1))elifj1:returndp(i-1,2)prices[i]# 注意分清递推的方向和状态转移的方向else:returnmax(dp(i-1,2),dp(i-1,0)-prices[i])returnmax(dp(len(prices)-1,0),dp(len(prices)-1,1))classSolution:defmaxProfit(self,prices:List[int])-int:nlen(prices)ifn0:return0cachedefdp(i,j):# 第i天的状态j \in {0 ,1 ,2} 代表不持有且无冻结、不持有被冻结、持有ifi0andj2:return-prices[i]elifi0andj1:return0ifj0:returnmax(dp(i-1,0),dp(i-1,1))elifj1:returndp(i-1,2)prices[i]else:returnmax(dp(i-1,0)-prices[i],dp(i-1,2))# 这块少考虑了一种情况returnmax(dp(n-1,0),dp(n-1,1))
