代码随想录算法训练营第五十天|动态规划part10|● 123.买卖股票的最佳时机III ● 188.买卖股票的最佳时机IV

**代码随想录算法训练营第五十天 | 动态规划 Part10**

**●123.买卖股票的最佳时机III ●188.买卖股票的最佳时机IV**

在前面的几篇文章中，我们已经学习了动态规划的基本概念和应用。今天，我们将继续深入探讨动态规划的应用，特别是通过两个经典问题：123.买卖股票的最佳时机III 和188.买卖股票的最佳时机IV。

**1.买卖股票的最佳时机III**

在这个问题中，我们需要找到一组交易日志中，能够获得最大利润的买卖策略。具体来说，我们有一个数组 `prices`，其中每个元素代表某一天的股价。如果我们可以在第 i 天买入，并在第 j 天（j > i）卖出，那么我们就能获得利润为 `prices[j] - prices[i]` 的交易。

我们的目标是找到能够获得最大利润的买卖策略，即使我们只能进行一次交易。这个问题与前面的122.买卖股票的最佳时机II 类似，但现在我们允许在任何时候进行交易，而不仅仅是在第一个交易日之后。

**解决方案**

为了解决这个问题，我们可以使用动态规划来找到最大利润。我们定义一个数组 `dp`，其中每个元素 `dp[i]` 表示到达第 i 天时的最大利润。如果我们在第 i 天买入，并在第 j 天卖出，那么我们的利润就是 `prices[j] - prices[i]`。

我们可以使用以下公式来计算 `dp[i]`：

dp[i] = max(dp[i-1], prices[i])

这里，我们有两种选择：要么我们不进行任何交易（即 `dp[i-1]`），要么我们在第 i 天买入，并在某一天 j (j > i) 卖出。由于我们只允许进行一次交易，因此我们的利润将取决于我们是否在第 i 天买入。

**代码示例**

def maxProfit(prices):
 if not prices:
 return0 dp = [0] * len(prices)
 for i in range(1, len(prices)):
 dp[i] = max(dp[i-1], prices[i])
 return dp[-1]

**2.买卖股票的最佳时机IV**

在这个问题中，我们需要找到一组交易日志中，能够获得最大利润的买卖策略。具体来说，我们有一个数组 `prices`，其中每个元素代表某一天的股价。如果我们可以在第 i 天买入，并在第 j 天（j > i）卖出，那么我们就能获得利润为 `prices[j] - prices[i]` 的交易。

我们的目标是找到能够获得最大利润的买卖策略，即使我们只能进行一次交易。这个问题与前面的123.买卖股票的最佳时机III 类似，但现在我们允许在任何时候进行交易，而不仅仅是在第一个交易日之后。

**解决方案**

为了解决这个问题，我们可以使用动态规划来找到最大利润。我们定义两个数组 `buy` 和 `sell`，其中每个元素 `buy[i]` 表示到达第 i 天时的最大买入利润，如果我们在某一天 j (j < i) 卖出，则 `sell[i]` 表示到达第 i 天时的最大卖出利润。

我们可以使用以下公式来计算 `buy[i]` 和 `sell[i]`：

buy[i] = max(buy[i-1], -prices[i])
sell[i] = max(sell[i-1], buy[i-1] + prices[i])

这里，我们有两种选择：要么我们不进行任何交易（即 `buy[i-1]` 和 `sell[i-1]`），要么我们在第 i 天买入或卖出。

**代码示例**

def maxProfit(prices):
 if not prices:
 return0 buy = [float('-inf')] * len(prices)
 sell = [0] * len(prices)
 for i in range(1, len(prices)):
 buy[i] = max(buy[i-1], -prices[i])
 sell[i] = max(sell[i-1], buy[i-1] + prices[i])
 return sell[-1]

通过以上两个例子，我们可以看到动态规划在解决买卖股票的最佳时机问题中非常有效。我们可以使用动态规划来找到最大利润，并且能够获得最优解。

**总结**

本文介绍了动态规划在解决买卖股票的最佳时机问题中的应用。通过两个经典问题：123.买卖股票的最佳时机III 和188.买卖股票的最佳时机IV，我们可以看到动态规划在解决这些问题中非常有效。我们可以使用动态规划来找到最大利润，并且能够获得最优解。

**参考**

* [LeetCode]( />* [LintCode](