121.买卖股票的最佳时机

发表于 分类于
这是文章开头，显示在主页面，详情请点击此处。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        # 经典的股票问题，动态规划；
        # 为了方便状态能够连续转移，定义 d[i][0]为第i天持有该股票手中的最大金额，d[i][1]为第i天不持有该股票手里的最大金额，因为初始手里没有钱，最后手里的钱都是利润；
        # 注意题意： 只会买入一次，还有只会卖出一次；
        # d[i][0] = 前一天就持有，或者当天买入,取两者最大者，注意：在只买一次的情况下，买入只可能是0-prices[i]；
        # d[i][1] = 前一天就已经不持有，或者当天卖出,取两者最大者；
        # 初始化 d[0][0]=-price[0];d[0][1]=0;其余为了不影响递推扩增，都定义为0；
        d = [ [0,0] for _ in range(len(prices))] 
        d[0][0] = -prices[0]
        for i in range(1,len(prices)):   # 从前往后遍历因为 前一天状态决定了后一天的状态；
            d[i][0] = max(d[i-1][0],0-prices[i])    # 注意：股票只买卖一次，第一次买入的时候不需要附加状态转移。
            d[i][1] = max(d[i-1][1],d[i-1][0]+prices[i])
            print(d[i])
        return max(d[len(prices)-1][0],d[len(prices)-1][1])