LeetCode 动态规划详解：原理、应用与实战技巧

引言

动态规划（Dynamic Programming，简称 DP）是一种通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。它常常适用于有重叠子问题和最优子结构性质的问题。本文将深入探讨动态规划的基本原理、应用场景以及在 LeetCode 上的实际应用。

1. 动态规划的基本原理

动态规划的核心思想是将复杂问题分解成简单子问题，并存储子问题的解以避免重复计算。它通常遵循以下步骤：

  1. 定义状态
  2. 找出状态转移方程
  3. 确定初始条件和边界情况
  4. 确定计算顺序
  5. 实现代码

2. 动态规划的常见类型

  1. 线性 DP：如最长递增子序列
  2. 区间 DP：如最长回文子串
  3. 背包 DP：如 0-1 背包问题
  4. 树形 DP：如二叉树的最大路径和
  5. 状态压缩 DP：如旅行商问题

3. LeetCode 实战应用

3.1 LeetCode 70. Climbing Stairs

这是一个经典的动态规划入门问题。

1
2
3
4
5
6
7
8
9
10
class Solution:
    def climbStairs(self, n: int) -> int:
        if n <= 2:
            return n
        dp = [0] * (n + 1)
        dp[1] = 1
        dp[2] = 2
        for i in range(3, n + 1):
            dp[i] = dp[i-1] + dp[i-2]
        return dp[n]

3.2 LeetCode 322. Coin Change

这是一个典型的背包问题变种。

1
2
3
4
5
6
7
8
9
10
class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        dp = [float('inf')] * (amount + 1)
        dp[0] = 0
        
        for coin in coins:
            for x in range(coin, amount + 1):
                dp[x] = min(dp[x], dp[x - coin] + 1)
        
        return dp[amount] if dp[amount] != float('inf') else -1

3.3 LeetCode 5. Longest Palindromic Substring

这是一个经典的区间 DP 问题。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution:
    def longestPalindrome(self, s: str) -> str:
        n = len(s)
        dp = [[False] * n for _ in range(n)]
        ans = ""
        
        for l in range(n):
            for i in range(n):
                j = i + l
                if j >= n:
                    break
                if l == 0:
                    dp[i][j] = True
                elif l == 1:
                    dp[i][j] = (s[i] == s[j])
                else:
                    dp[i][j] = (dp[i+1][j-1] and s[i] == s[j])
                
                if dp[i][j] and l + 1 > len(ans):
                    ans = s[i:j+1]
        
        return ans

3.4 LeetCode 198. House Robber

这是一个经典的线性 DP 问题。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    def rob(self, nums: List[int]) -> int:
        if not nums:
            return 0
        if len(nums) <= 2:
            return max(nums)
        
        dp = [0] * len(nums)
        dp[0] = nums[0]
        dp[1] = max(nums[0], nums[1])
        
        for i in range(2, len(nums)):
            dp[i] = max(dp[i-1], dp[i-2] + nums[i])
        
        return dp[-1]

4. 动态规划的应用场景

  1. 最优化问题：如最长公共子序列、背包问题等
  2. 计数问题：如路径总数、硬币组合数等
  3. 概率问题：如股票交易、骰子游戏等
  4. 游戏策略：如石子游戏、翻转游戏等

5. 动态规划的优化技巧

  1. 状态压缩：使用滚动数组或位运算压缩状态，减少空间复杂度
  2. 记忆化搜索：自顶向下的 DP 实现，适合某些特定问题
  3. 前缀和/差分：预处理数组，加速区间查询和修改
  4. 单调队列/单调栈：优化特定类型的 DP 问题
  5. 斜率优化：用于优化某些特殊形式的 DP 转移方程

6. 动态规划与其他算法的比较

  1. 动态规划 vs 贪心：DP 考虑所有可能的解，而贪心每步选择局部最优解
  2. 动态规划 vs 分治：DP 通常自底向上，而分治通常自顶向下且问题相互独立
  3. 动态规划 vs 回溯：DP 通常用于求最优解，而回溯常用于求所有可能的解

7. 动态规划的解题步骤

  1. 分析问题：确定问题是否适合用 DP 解决
  2. 定义状态：明确 DP 数组的含义
  3. 确定转移方程：找出状态之间的关系
  4. 初始化：设置初始状态和边界条件
  5. 确定遍历顺序：通常是自底向上
  6. 实现代码：根据以上步骤编写代码
  7. 优化：考虑是否可以优化空间或时间复杂度

8. 常见的动态规划模式

  1. 线性 DP：如最长递增子序列、编辑距离
  2. 区间 DP：如最长回文子序列、石子合并
  3. 树形 DP：如二叉树的最大路径和、树的直径
  4. 状态压缩 DP：如旅行商问题、集合划分
  5. 数位 DP：如数字 1 的个数、可被 K 整除的数字
  6. 概率 DP：如股票买卖、骰子游戏
  7. 博弈 DP：如石子游戏、Nim 游戏

9. 动态规划的难点与解决策略

  1. 状态定义不清：尝试多种状态定义，选择最合适的
  2. 转移方程不明确：从简单例子开始，归纳出一般规律
  3. 边界条件处理：特别注意初始化和特殊情况
  4. 空间优化困难：先实现朴素解法，再考虑优化
  5. 问题抽象能力：多做题，积累经验，提高抽象思维能力

结语

动态规划是一种强大的算法设计技巧，特别适合解决具有重叠子问题和最优子结构的问题。通过本文的学习，我们深入了解了动态规划的基本原理、LeetCode 实战应用以及各种技巧和注意事项。在实际应用中，要根据具体问题的特点，选择合适的 DP 策略，并不断练习以提高解题能力。记住，动态规划的精髓在于将复杂问题分解为简单子问题，并通过巧妙的状态设计和转移来解决问题。通过不断练习和总结，我们可以在算法解题中越来越熟练地运用动态规划思想，解决各种复杂问题。