动态规划与贪心算法解股票买卖问题

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(index1, False), # 卖出 dfs(index1, True) # 持有 ) else: # 可以选择买入或观望 return max( -prices[index] dfs(index1, True), # 买入 dfs(index1, False) # 观望 ) return dfs(0, False)2.2 复杂度问题这种解法的时间复杂度是O(2^n)因为每个状态都会产生两个分支。对于n100的情况计算量将达到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 cash4. 贪心算法的巧妙解法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 profit4.3 算法分析时间复杂度O(n)只需一次遍历空间复杂度O(1)只使用常数空间适用性这种解法仅适用于本题的特殊条件无限次交易不适用于交易次数受限的情况5. 不同解法的对比与选择解法类型时间复杂度空间复杂度适用场景扩展性暴力递归O(2^n)O(n)理论理解无动态规划O(n)O(n)或O(1)通用解法强贪心算法O(n)O(1)本题特例弱实际面试中建议优先实现动态规划解法因为它展示了完整的解题思路且适用于各种变种题。如果时间紧张可以最后提到贪心解法作为优化。6. 常见错误与调试技巧6.1 边界条件处理空数组或单元素数组应直接返回0单调递减数组利润应为0连续相同价格时应不影响结果6.2 易错点初始化错误hold初始值应为-prices[0]而非0索引越界注意循环从1开始而非0状态混淆分清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. 实战建议与学习路径建议按照以下顺序刷题买卖股票的最佳时机单次交易本题无限交易买卖股票的最佳时机 III两次交易买卖股票的最佳时机 IVk次交易最佳买卖股票时机含冷冻期买卖股票的最佳时机含手续费理解核心模式后可以尝试其他动态规划问题打家劫舍系列零钱兑换最长递增子序列在力扣讨论区查看高质量题解时重点关注状态定义的合理性边界条件的处理空间优化的方法对于这类动态规划问题我个人的经验是多画状态转移图。把每个状态用节点表示转移操作用箭头表示这样能直观理解状态之间的关系。在实际面试中即使不能立即写出最优解也应该先给出暴力解法再逐步优化展示完整的思考过程。