LeetCode股票交易类算法题目总结：一次交易、两次交易与无数次交易

在LeetCode中，股票交易类题目是常见的算法题目之一。这类题目主要考察了动态规划、数学计算和逻辑推理能力。本文将总结一次交易、两次交易和无数次交易的股票交易类题目的解题思路和关键点。
一、一次交易
一次交易的题目通常要求计算在给定时间段内购买和卖出股票的最大利润。这类题目可以使用贪心算法来解决。关键点在于找到最低买入价和最高卖出价，以及它们的对应时间。
例如，假设我们有一个数组表示每一天的股票价格，我们需要找到最大的利润。可以使用贪心策略，遍历数组，对于每一天的价格，如果比前一天低，就买入；如果比前一天高，就卖出。最后得到的最大利润即为所求。
二、两次交易
两次交易的题目要求在给定时间段内进行两次买卖操作，使得利润最大化。这类题目可以使用动态规划来解决。关键点在于状态转移方程的设计和状态压缩技巧的使用。
例如，假设我们有一个数组表示每一天的股票价格，我们需要找到最大的利润。可以使用动态规划算法，定义状态dp[i][j]，表示在i天结束时持有j股股票的最大利润。状态转移方程可以设计为：dp[i][j] = max(dp[i-1][j], dp[i-1][j-1] + prices[i])，表示在i天持有j股股票的最大利润等于前一天持有j股的最大利润或者前一天持有j-1股并在i天卖出股票的最大利润加上i天的价格。最后得到的最大利润即为所求。
三、无数次交易
无数次交易的题目要求在给定时间段内进行任意次数的买卖操作，使得利润最大化。这类题目可以使用动态规划或数学方法来解决。关键点在于理解题目的本质和寻找合适的解决方法。
例如，假设我们有一个数组表示每一天的股票价格，我们需要找到最大的利润。可以使用动态规划算法，定义状态dp[i][j]，表示在i天结束时持有j股股票的最大利润。状态转移方程可以设计为：dp[i][j] = max(dp[i-1][j], dp[i-1][j-1] + prices[i])，表示在i天持有j股股票的最大利润等于前一天持有j股的最大利润或者前一天持有j-1股并在i天卖出股票的最大利润加上i天的价格。最终的答案即为dp[n-1][0]，其中n为数组prices的长度。
总结：
解决股票交易类题目需要理解题目的本质和要求，选择合适的算法和数据结构来解决问题。对于一次交易的题目，可以使用贪心算法；对于两次交易的题目，可以使用动态规划算法；对于无数次交易的题目，可以根据具体情况选择动态规划或数学方法来求解。在实际应用中，还需要考虑一些额外的因素，如手续费、滑点等，这些因素可能会影响最终的利润。因此，在解决这类问题时，需要综合考虑各种因素，选择最合适的解决方法。