LeetCode股票买卖问题：动态规划解法

在LeetCode中的编程面试题集中，"121. Best Time to Buy and Sell Stock" 和 "122. Best Time to Buy and Sell Stock II" 是两个经典的股票买卖问题，涉及动态规划算法的应用。这两个题目都是关于股票投资策略，目标是在给定的股票价格序列中找到最优化的买入和卖出时机，以获得最大的收益。 1. **题目1: 121. Best Time to Buy and Sell Stock** - 这道题考察的是单次买卖股票的问题。函数`maxProfit(prices)`接收一个整数数组`prices`，表示股票在不同日期的价格。通过遍历整个价格序列，找到最低价`min_price`，然后计算在每一步卖出时的利润（当前价格减去最低价）。最后返回最大的利润`max_profit`。这是一个简单的线性时间复杂度O(n)解决方案，适合初学者理解基本的动态规划思想。 2. **题目2: 122. Best Time to Buy and Sell Stock II** - 在这道题中，情况变得更加复杂，允许进行多次交易但有最大交易次数限制（K次）。题目要求实现一个名为`Solution`的类，其中包含一个方法`maxProfit`。这里采用了二维动态规划的方法，状态转移方程涉及三种决策：持有（sell）、不持有（rest）和买入（buy）。`dp[i][k][s]`表示在第i天持有k个股票（0或1）后的最大利润，其中`s`代表当前是持有还是不持有状态。状态转移规则包括考虑前一天的状态以及当前价格的变化，如： - 当前不持有且可交易时，`dp[i][k][0] = max(dp[i-1][k][0], dp[i-1][k][1] + prices[i])` - 当前持有且可交易时，`dp[i][k][1] = max(dp[i-1][k][1], dp[i-1][k-1][0] - prices[i])` - 基本情况初始化为：`dp[-1][k][0] = 0`，`dp[-1][k][1] = -inf`，`dp[i][0][0] = 0`。 这些题目展示了如何在实际编程面试中运用动态规划来解决具有决策选择的问题。它们不仅锻炼了算法设计和代码实现能力，还涉及到对问题空间的划分和状态转移的理解。对于准备面试的应聘者来说，掌握这类问题的解决方案将有助于提升其在大厂面试中的竞争力。