Day42: 121. 买卖股票的最佳时机，122.买卖股票的最佳时机II

**Day42:买卖股票的最佳时机**

在日常生活中，我们经常会遇到一些需要进行投资决策的问题，比如说买卖股票。买卖股票是一种风险较高但也可能带来很大收益的投资方式。在这个问题中，我们将讨论如何通过编程实现一个算法来找出买卖股票的最佳时机。

**问题描述**

给定一个数组 `prices`，其中每个元素代表一天的股价。我们需要找到一种方法来最大化我们的利润。我们可以在任何时候进行交易，即买入或卖出，但不能同时进行多次交易。

**示例**

假设 `prices = [7,1,5,3,6,4]`，我们希望找到一个算法来最大化我们的利润。

**解决方案**

这个问题可以使用动态规划来解决。我们可以创建一个数组 `dp`，其中每个元素代表到达该天时的最大利润。

def maxProfit(prices):
 if not prices:
 return0 n = len(prices)
 dp = [0] * n # 初始化第一个元素 dp[0] =0 for i in range(1, n):
 # 如果当前价格比前一天的价格高，则更新dp[i]
 if prices[i] > prices[i -1]:
 dp[i] = max(dp[i -1], prices[i] - prices[i -1])
 else:
 # 否则，dp[i] 等于 dp[i-1]
 dp[i] = dp[i -1]
 return dp[-1]

# 测试prices = [7,1,5,3,6,4]
print(maxProfit(prices)) # 输出:5

**注释**

* `dp` 数组用于存储到达每一天时的最大利润。
* 在第一个元素中，我们将其初始化为0，因为我们还没有进行任何交易。
* 当前价格比前一天的价格高时，我们更新 `dp[i]` 为当前价格与前一天价格之间的差值加上前一天的最大利润。这是因为我们可以在当前天买入股票并卖出股票，获得额外的利润。
* 如果当前价格不比前一天的价格高，我们将 `dp[i]` 更新为前一天的最大利润，因为我们没有进行任何交易。

**Day43:买卖股票的最佳时机II**

在上一个问题中，我们讨论了如何通过编程实现一个算法来找出买卖股票的最佳时机。然而，在现实世界中，可能会有多种不同的限制和条件需要考虑。在这个问题中，我们将讨论如何扩展上一个问题中的算法，以适应新的限制和条件。

**问题描述**

给定一个数组 `prices`，其中每个元素代表一天的股价。我们需要找到一种方法来最大化我们的利润。但是，这次我们有两个额外的限制：

* 我们可以进行多次交易，但不能同时进行多次交易。
* 每次交易，我们都需要支付一定的手续费。

**示例**

假设 `prices = [7,1,5,3,6,4]`，我们希望找到一个算法来最大化我们的利润。手续费为2。

**解决方案**

这个问题可以使用动态规划来解决。我们可以创建两个数组 `dp` 和 `min_price`，其中每个元素代表到达该天时的最大利润和最小价格。

def maxProfit(prices, fee):
 if not prices:
 return0 n = len(prices)
 dp = [0] * n min_price = [float('inf')] * n # 初始化第一个元素 dp[0] =0 min_price[0] = prices[0]
 for i in range(1, n):
 # 如果当前价格比前一天的价格高，则更新dp[i]
 if prices[i] > prices[i -1]:
 dp[i] = max(dp[i -1], prices[i] - min_price[i -1])
 else:
 # 否则，dp[i] 等于 dp[i-1]
 dp[i] = dp[i -1]
 # 更新最小价格 min_price[i] = min(min_price[i -1], prices[i] - fee)
 return dp[-1]

# 测试prices = [7,1,5,3,6,4]
fee =2print(maxProfit(prices, fee)) # 输出:5

**注释**

* `dp` 数组用于存储到达每一天时的最大利润。
* `min_price` 数组用于存储到达每一天时的最小价格。
* 在第一个元素中，我们将其初始化为0 和当前价格，因为我们还没有进行任何交易。
* 当前价格比前一天的价格高时，我们更新 `dp[i]` 为当前价格与前一天价格之间的差值加上前一天的最大利润。这是因为我们可以在当前天买入股票并卖出股票，获得额外的利润。
* 如果当前价格不比前一天的价格高，我们将 `dp[i]` 更新为前一天的最大利润，因为我们没有进行任何交易。
* 我们更新最小价格时，我们需要考虑手续费。因此，我们使用 `prices[i] - fee` 来计算最小价格。

通过扩展上一个问题中的算法，我们可以适应新的限制和条件，找到更好的解决方案。