买卖股票的最佳时机1

【买卖股票的最佳时机1】 在LeetCode的第121题中，我们面临的挑战是找到在最多只能进行一次买卖操作的情况下，从给定的一系列股票价格中获得的最大利润。这个问题可以使用动态规划来解决，但因为交易次数仅限一次，所以交易次数的状态实际上可以忽略。 在动态规划的解决方案中，我们可以定义两个状态：`dp[i][0]`表示在第i天结束时不持有股票的最大利润，`dp[i][1]`表示在第i天结束时持有股票的最大利润。但由于交易次数不受限制，我们只需要关心不持有股票的状态，因为一旦我们卖出股票，我们就不能再买回了，所以我们只需关注`dp[i][0]`即可。 在题目描述给出的代码实现中，我们用`pre`变量记录到目前为止遇到的最小价格，`res`变量记录当前的最大利润。遍历股票价格数组，如果当前价格`prices[i]`小于`pre`，则更新`pre`为当前价格；否则，计算`prices[i] - pre`的差值，并与`res`比较，取较大值作为新的`res`。最后返回`res`作为最大利润。 【买卖股票的最佳时机Ⅱ】 LeetCode的第122题要求在可以进行多次买卖操作的情况下，找到最大的利润。这个问题同样可以用动态规划或贪心策略解决。 1) 贪心策略： 在这种策略下，我们观察到每次卖出股票的时机应该是当前价格高于前一个价格的时候。因此，我们遍历价格数组，如果当前价格`prices[i]`大于前一个价格`prices[i-1]`，就将差值`prices[i] - prices[i-1]`累加到结果`res`上。最后返回`res`作为最大利润。 2) 动态规划策略： 在这种策略中，我们仍然可以定义两个状态，但这次交易次数不再是无限的，而是可以进行多次交易。状态转移方程如下： - `dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i])`：表示在第i天结束时不持有股票的最大利润，可以从前一天不持有股票或者前一天持有并在当天卖出中选择较大的利润。 - `dp[i][1] = max(dp[i-1][1], dp[i-1][0] - prices[i])`：表示在第i天结束时持有股票的最大利润，可以从前一天持有股票或者前一天不持有并在当天买入中选择较大的利润。 然而，由于可以进行多次交易，这里我们确实需要考虑两个状态。在遍历过程中，我们需要维护这两个状态，最后返回`dp[n-1][0]`作为最大利润。 总结： 这两道题都是关于股票交易的问题，但它们的主要区别在于交易次数的限制。第一题要求一次交易，我们只需要关注卖出的最佳时机；而第二题允许多次交易，我们需要更复杂的策略，如贪心或动态规划，来决定何时买入和卖出以最大化利润。在实际编程中，理解和应用这些策略对于解决类似问题至关重要。