力扣股票问题动态规划解法总结

"本文主要探讨了LEETCODE力扣网站上的股票问题，涉及动态规划的解题策略，并给出了典型的状态转移方程。" 在LEETCODE力扣网站上，股票问题是一个常见的动态规划主题，这类问题通常围绕着如何在给定的股票价格序列中寻找最佳的买卖时机以获得最大利润。以下将详细介绍这类问题的一般思路和关键知识点。 首先，我们需要理解动态规划的基本概念。动态规划是一种解决问题的方法，通过将大问题分解为小问题并存储中间结果，以避免重复计算。在股票问题中，我们通常会定义一个状态数组来表示在不同天数、不同交易次数下的最大利润。 例如，我们可以使用一个三维数组`dp[i][k][state]`来表示第`i`天，进行了`k`次交易后，处于`state`状态（0表示未持有股票，1表示持有股票）的最大利润。状态转移方程如下： 1. `dp[i][k][0] = max(dp[i-1][k][0], dp[i-1][k][1] + prices[i])` 这个方程表示在第`i`天结束时未持有股票的情况。两种可能的情况是： - 昨天也没有持有股票，即`dp[i-1][k][0]`。 - 昨天持有股票并在今天卖出，利润为`dp[i-1][k][1] + prices[i]`。 2. `dp[i][k][1] = max(dp[i-1][k][1], dp[i-1][k-1][0] - prices[i])` 这个方程表示在第`i`天结束时持有股票的情况。同样有两种可能： - 昨天也持有股票，即`dp[i-1][k][1]`。 - 昨天未持有股票但今天买入，利润为`dp[i-1][k-1][0] - prices[i]`，交易次数减1。 基本边界条件如下： - `dp[-1][k][0] = 0`，表示在交易开始前，没有利润。 - `dp[-1][k][1] = -infinity`，表示在交易开始前，不可能持有股票。 - `dp[i][0][0] = 0`，不允许交易时，利润为0。 - `dp[i][0][1] = -infinity`，不允许交易时，不可能持有股票。 以121.买卖股票的最佳时机为例，给定一个股票价格数组`prices`，目标是找到最大利润。在这个问题中，我们只允许进行一次交易，所以`k`为1。通过上述动态规划策略，我们可以遍历数组并更新`dp`数组，最终得到`dp[days-1][1][0]`，即在最后一天结束时未持有股票的最大利润。 对于更复杂的情况，如多次交易或有交易限制（如冷冻期），我们可以基于这些基础方程进行扩展。例如，122.买卖股票的最佳时机II允许每天交易一次，而123.买卖股票的最佳时机III则引入了冷冻期的概念，卖出股票后一段时间内不能再次买入。这些题目虽然增加了复杂性，但核心思想仍然是通过状态转移方程求解最大利润。 理解和掌握动态规划在股票问题中的应用，对于解决LEETCODE力扣上的相关挑战至关重要。通过不断练习和分析，可以提升解决此类问题的能力。