## leetcode：买卖股票的最佳时机 III（python）

LeetCode 股票 最佳 买卖 最佳时机

## 2. 思路（动态规划）

### 2.1 python 代码

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

### 2.2 优化代码

``````class Solution:
def maxProfit(self, prices: List[int]) -> int:
if len(prices) == 0:
return 0
k = 2
n = len(prices)
dp_i_1_0 = 0
dp_i_1_1 = -prices[0]
dp_i_2_0 = 0
dp_i_2_1= -prices[0]
for i in range(1,n):
dp_i_1_0 = max(dp_i_1_0,dp_i_1_1 + prices[i])
dp_i_1_1 = max(dp_i_1_1,-prices[i])
dp_i_2_0 = max(dp_i_2_0,dp_i_2_1 + prices[i])
dp_i_2_1 = max(dp_i_2_1,dp_i_1_0 - prices[i])
return dp_i_2_0
``````

https://blog.csdn.net/ggdhs/article/details/92618827