LeetCode 买卖股票问题

1
2
3
4
5
6
7
8

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        ## 动态规划
        dp_0, dp_1 = 0, float('-inf')
        for price in prices:
            dp_0 = max(dp_0, dp_1+price)
            dp_1 = max(dp_1, -price)
        return dp_0

1
2
3
4
5
6

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        dp_0, dp_1 = 0, float('-inf')
        for price in prices:
            dp_0, dp_1 = max(dp_0, dp_1+price), max(dp_1, dp_0-price)
        return dp_0

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        n, K = len(prices), 2
        dp = [ [ [0]*2 for _ in range(K+1) ] for _ in range(n) ]
        for i in range(n):
            for k in range(K, 0, -1):
                if not i:
                    dp[i][k][0], dp[i][k][1] = 0, -prices[i]
                    continue
                dp[i][k][0] = max(dp[i-1][k][0], dp[i-1][k][1]+prices[i])
                dp[i][k][1] = max(dp[i-1][k][1], dp[i-1][k-1][0]-prices[i])
        return dp[n-1][K][0]

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

class Solution:
    def maxProfitInf(self, prices: List[int]) -> int:
        dp_0, dp_1 = 0, float('-inf')
        for price in prices:
            dp_0, dp_1 = max(dp_0, dp_1+price), max(dp_1, dp_0-price)
        return dp_0
    
    def maxProfit(self, K: int, prices: List[int]) -> int:
        n = len(prices)
        if K > n//2:
            return self.maxProfitInf(prices)
        dp = [ [ [0]*2 for _ in range(K+1) ] for _ in range(n) ]
        for i in range(n):
            for k in range(K, 0, -1):
                if not i:
                    dp[i][k][0], dp[i][k][1] = 0, -prices[i]
                    continue
                dp[i][k][0] = max(dp[i-1][k][0], dp[i-1][k][1]+prices[i])
                dp[i][k][1] = max(dp[i-1][k][1], dp[i-1][k-1][0]-prices[i])
        return dp[n-1][K][0]