LeetCode 122. 买卖股票的最佳时机 IIPython3思路贪心由于可以无限次交易只要第二天价格比第一天高就可以在前一天买入、第二天卖出赚取差价。把所有相邻两天的正收益累加起来就是最大利润。例如[7,1,5,3,6,4]· 1 - 5 赚 4· 3 - 6 赚 3· 总利润 7Python3 实现贪心classSolution:defmaxProfit(self,prices:List[int])-int:profit0foriinrange(1,len(prices)):ifprices[i]prices[i-1]:profitprices[i]-prices[i-1]returnprofitPython3 实现动态规划用 dp0 表示当天不持股的最大利润dp1 表示当天持股的最大利润。classSolution:defmaxProfit(self,prices:List[int])-int:# dp0: 不持股dp1: 持股dp00dp1-prices[0]foriinrange(1,len(prices)):new_dp0max(dp0,dp1prices[i])new_dp1max(dp1,dp0-prices[i])dp0,dp1new_dp0,new_dp1returndp0关键点贪心法每一段上涨都拆成每天的正收益累加即可。动态规划状态转移· 不持股max(昨天不持股, 昨天持股 今天价格)· 持股max(昨天持股, 昨天不持股 - 今天价格)无限次交易买入时不需要考虑之前是否卖出因此 dp0 - prices[i] 可以直接用。复杂度· 时间O(n)遍历一次。· 空间贪心法 O(1)DP 法 O(1)。测试用例maxProfit([7,1,5,3,6,4])# 7maxProfit([1,2,3,4,5])# 4maxProfit([7,6,4,3,1])# 0