力扣网动态规划专题：2025 年高频题型全解析及代码优化

? 动态规划专题：2025 年高频题型全解析及代码优化

? 高频题型分类与核心思路

1. 背包问题变种：多维约束下的最优选择

• 状态定义：dp [i][j][k] 表示前 i 个物品中，重量不超过 j，时间不超过 k 的最大价值。
• 转移方程：对于每个物品，有选与不选两种情况。若选择第 i 个物品，则新的重量为 j - w_i，新的时间为 k - t_i，价值增加 v_i。状态转移方程为：
  python

  dp[i][j][k] = max(dp[i-][j][k], dp[i-][j-w_i][k-t_i] + v_i)
  
  
  
• 优化技巧：对于多维背包问题，可以通过压缩状态空间来减少内存使用。例如，将三维数组压缩为二维数组，利用滚动数组的思想，只保留当前层和上一层的数据。

2. 最长子序列系列：结合贪心与二分查找

• 传统 DP 方法：定义 dp [i] 为以第 i 个元素结尾的最长递增子序列长度，时间复杂度为 O (n²)。
• 优化方法：维护一个 tails 数组，其中 tails [i] 表示长度为 i+1 的递增子序列的最小尾部值。通过二分查找更新 tails 数组，时间复杂度可降至 O (n log n)。
  python

  def lengthOfLIS(nums):
      tails = []
      for num in nums:
          left, right = , len(tails)
          while left < right:
              mid = (left + right) // 
              if tails[mid] < num:
                  left = mid + 
              else:
                  right = mid
          if left == len(tails):
              tails.append(num)
          else:
              tails[left] = num
      return len(tails)
  
  
  

3. 树形动态规划：处理层次结构问题

• 状态定义：对于每个节点，定义两个状态：选该节点时的最大金额（selected）和不选该节点时的最大金额（not_selected）。
• 转移方程：
  python

  selected = node.val + not_selected_left + not_selected_right
  not_selected = max(selected_left, not_selected_left) + max(selected_right, not_selected_right)
  
  
  
• 递归实现：通过后序遍历递归处理每个节点，返回当前节点的 selected 和 not_selected 值。

? 代码优化技巧与实践

1. 空间优化：滚动数组与状态压缩

• 传统 DP 方法：使用二维数组 dp [i][j]，空间复杂度为 O (mn)。
• 滚动数组优化：将二维数组压缩为一维数组，每次只保留当前行的数据。空间复杂度降至 O (n)。
  python

  def uniquePaths(m, n):
      dp = [] * n
      for i in range(, m):
          for j in range(, n):
              dp[j] += dp[j-]
      return dp[-]
  
  
  

2. 时间优化：二分查找与双指针

• 传统 DP 方法：时间复杂度为 O (mn)。
• 优化方法：当其中一个字符串长度远小于另一个时，可以利用哈希表和二分查找优化。例如，将较短字符串的字符位置记录下来，然后在较长字符串中查找最长递增子序列。

3. 预处理与记忆化搜索

• 递归方法：时间复杂度为 O (2ⁿ)，存在大量重复计算。
• 记忆化搜索优化：使用缓存存储已计算的结果，时间复杂度降至 O (n)。
  python

  from functools import lru_cache
  
  @lru_cache(maxsize=None)
  def fib(n):
      if n <= :
          return n
      return fib(n-) + fib(n-)
  
  
  

? 常见错误与避坑指南

1. 状态定义不清晰

2. 边界条件处理不当

3. 遍历顺序错误

4. 空间优化导致的覆盖问题

? 2025 年新趋势与题型预测

1. 动态规划与其他算法的结合

2. 多维度约束与动态规划

3. 实时数据处理与动态规划

? 学习资源与实践建议

1. 力扣官方题解：力扣网提供了详细的题解和讨论区，可参考其他用户的优秀解法，学习不同的优化思路。
2. 算法书籍：《算法导论》、《动态规划：从入门到精通》等书籍系统讲解了动态规划的原理和应用。
3. 在线课程：Coursera、慕课网等平台的算法课程，结合视频讲解和编程实践，帮助深入理解动态规划。
4. 模拟比赛：参加力扣周赛、全球编程挑战赛等，在实战中提升解题速度和应变能力。