企业官网建设流程全解析

1. 问题背景与核心需求

股票交易是算法面试中的经典题型，122题作为力扣热题100中的高频考点，考察的是动态规划思想在实际问题中的应用。题目要求：给定一个数组prices，其中prices[i]表示某支股票第i天的价格，设计算法计算能获得的最大利润。与121题（单次交易）不同，本题允许进行多次交易（但必须在再次购买前出售掉之前的股票）。

举个例子，对于输入prices = [7,1,5,3,6,4]，最优策略是在第2天买入（价格1）、第3天卖出（价格5），利润4；然后在第4天买入（价格3）、第5天卖出（价格6），利润3。总利润为7。这就是典型的"低买高卖"多次操作场景。

2. 暴力解法与复杂度分析

2.1 递归穷举思路

最直观的方法是递归尝试所有可能的买卖组合。对于每一天，我们有三中选择：买入、卖出或持有。递归函数需要记录当前是否持有股票以及持有价格。

def maxProfit(prices): def dfs(index, has_stock): if index == len(prices): return 0 if has_stock: # 可以选择卖出或持有 return max( prices[index] + dfs(index+1, False), # 卖出 dfs(index+1, True) # 持有 ) else: # 可以选择买入或观望 return max( -prices[index] + dfs(index+1, True), # 买入 dfs(index+1, False) # 观望 ) return dfs(0, False)

2.2 复杂度问题

这种解法的时间复杂度是O(2^n)，因为每个状态都会产生两个分支。对于n=100的情况，计算量将达到1.26e30次操作，完全不可行。这引出了我们需要更高效的算法。

3. 动态规划标准解法

3.1 状态定义与转移方程

动态规划是解决这类问题的标准方法。我们定义两个状态：

• dp[i][0]：第i天结束时未持有股票的最大利润
• dp[i][1]：第i天结束时持有股票的最大利润

状态转移方程：

dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i]) # 前一天未持有或当天卖出 dp[i][1] = max(dp[i-1][1], dp[i-1][0] - prices[i]) # 前一天持有或当天买入

3.2 实现代码

def maxProfit(prices): n = len(prices) if n < 2: return 0 dp = [[0]*2 for _ in range(n)] dp[0][0] = 0 dp[0][1] = -prices[0] for i in range(1, n): dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i]) dp[i][1] = max(dp[i-1][1], dp[i-1][0] - prices[i]) return dp[-1][0]

3.3 空间优化

注意到dp[i]只依赖于dp[i-1]，可以优化空间到O(1)：

def maxProfit(prices): cash, hold = 0, -prices[0] for price in prices[1:]: cash, hold = max(cash, hold + price), max(hold, cash - price) return cash

4. 贪心算法的巧妙解法

4.1 核心思路

观察价格曲线可以发现：总利润等于所有上升区间的累加。比如[1,3,5]的利润4等于(3-1)+(5-3)=4。因此只需累加所有prices[i]>prices[i-1]的差值。

4.2 实现代码

def maxProfit(prices): profit = 0 for i in range(1, len(prices)): if prices[i] > prices[i-1]: profit += prices[i] - prices[i-1] return profit

4.3 算法分析

• 时间复杂度：O(n)，只需一次遍历
• 空间复杂度：O(1)，只使用常数空间
• 适用性：这种解法仅适用于本题的特殊条件（无限次交易），不适用于交易次数受限的情况

5. 不同解法的对比与选择

实际面试中，建议优先实现动态规划解法，因为它展示了完整的解题思路，且适用于各种变种题。如果时间紧张，可以最后提到贪心解法作为优化。

6. 常见错误与调试技巧

6.1 边界条件处理

• 空数组或单元素数组应直接返回0
• 单调递减数组利润应为0
• 连续相同价格时应不影响结果

6.2 易错点

1. 初始化错误：hold初始值应为-prices[0]而非0
2. 索引越界：注意循环从1开始而非0
3. 状态混淆：分清cash和hold的更新顺序

6.3 调试方法

建议打印dp表观察状态变化：

prices = [7,1,5,3,6,4] # 打印dp[i][0]和dp[i][1]的变化

7. 问题变种与扩展

7.1 交易费用

每次交易需要支付固定费用fee，只需修改状态转移方程：

cash = max(cash, hold + price - fee) # 卖出时扣除费用 hold = max(hold, cash - price)

7.2 冷却期

卖出后需要等待一天才能买入，状态需要增加"冷却"状态：

cash = max(cash, rest) # 前一天是冷却或继续不持有 hold = max(hold, cash_prev - price) # 只能用前天的cash买入 rest = hold_prev + price # 卖出进入冷却

7.3 交易次数限制

如最多完成k次交易，需要增加维度记录交易次数：

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])

8. 实战建议与学习路径

1. 建议按照以下顺序刷题：

   • 121. 买卖股票的最佳时机（单次交易）
   • 122. 本题（无限交易）
   • 123. 买卖股票的最佳时机 III（两次交易）
   • 188. 买卖股票的最佳时机 IV（k次交易）
   • 309. 最佳买卖股票时机含冷冻期
   • 714. 买卖股票的最佳时机含手续费

2. 理解核心模式后，可以尝试其他动态规划问题：

   • 打家劫舍系列
   • 零钱兑换
   • 最长递增子序列

3. 在力扣讨论区查看高质量题解时，重点关注：

   • 状态定义的合理性
   • 边界条件的处理
   • 空间优化的方法

对于这类动态规划问题，我个人的经验是多画状态转移图。把每个状态用节点表示，转移操作用箭头表示，这样能直观理解状态之间的关系。在实际面试中，即使不能立即写出最优解，也应该先给出暴力解法，再逐步优化，展示完整的思考过程。