算法题day49（6.4打卡：dp08)

一、leetcode刷题：

1.leetcode题目 121.买卖股票的最佳时机 . - 力扣（LeetCode）(easy）

解决：

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        cur_min = prices[0]
        maxx = 0
        for i in range(1,len(prices)):
            maxx = max(maxx,prices[i]-cur_min)
            cur_min = min(cur_min,prices[i])
        return maxx

2.leetcode题目 122.买卖股票的最佳时机II . - 力扣（LeetCode）(medium）

解决：

贪心算法：

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        summ = 0
        cur_min = prices[0]
        for i in range(1,len(prices)):
            cur_min = min(cur_min,prices[i])
            if prices[i] > cur_min:
                summ += prices[i] - cur_min
                cur_min = prices[i]
        return summ

动态规划：

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        dpf = [0]*len(prices)  ##当天无持仓时的最大资产
        dpg = [0]*len(prices)  ##当天持仓时的最大资产
        dpg[0] = -prices[0]
        for i in range(1,len(prices)):
            dpf[i] = max(dpf[i-1],dpg[i-1] + prices[i])
            dpg[i] = max(dpg[i-1],dpf[i-1] - prices[i])
        return dpf[len(prices)-1]

3.leetcdoe题目 123.买卖股票的最佳时机III （medium):

动态规划：

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        n = len(prices)
        buy1 = -prices[0]
        buy2 = -prices[0]
        sell1=0
        sell2 = 0
        for p in prices:
            buy1 = max(buy1,-p)
            sell1 = max(sell1,buy1 + p)
            buy2 = max(buy2,sell1-p)
            sell2 = max(sell2,buy2+p)
        return sell2