强化学习篇---动态规划算法

Ronin-Lotus

998人浏览 · 2026-02-25 23:37:51

Ronin-Lotus · 2026-02-25 23:37:51 发布

动态规划深度解析：分而治之的智慧

什么是动态规划？

动态规划（Dynamic Programming）是一种通过将复杂问题分解为更简单的子问题，并存储子问题的解来避免重复计算的方法。

想象一下：

你要爬10层楼梯，一次可以爬1阶或2阶 → 爬到第10层的方法数 = 爬到第9层的方法数 + 爬到第8层的方法数
你要从北京到上海的最短路径 → 经过某个城市的最短路径 = 到该城市的最短路径 + 从该城市到上海的最短路径
你要整理一堆文件 → 先把文件分成几小堆，整理好小堆，再合并

核心思想：记住已经算过的答案，避免重复劳动

生活中的动态规划

例子1：斐波那契数列

普通递归（傻办法）：
F(5) = F(4) + F(3)
     = [F(3) + F(2)] + [F(2) + F(1)]
     = [[F(2) + F(1)] + F(2)] + [F(2) + 1]
     = ...

动态规划（聪明办法）：
F(1)=1, F(2)=1
F(3)=F(2)+F(1)=2
F(4)=F(3)+F(2)=3
F(5)=F(4)+F(3)=5

例子2：背包问题

你有一个能装10kg的背包，有几件物品：

书本：3kg，价值5元
电脑：4kg，价值8元
相机：2kg，价值3元
衣服：5kg，价值6元

问题：怎么装价值最大？

动态规划思路：

先考虑只装前1件物品
再考虑装前2件物品时，要不要加第2件
逐步扩展到所有物品

动态规划的核心要素

1. 最优子结构（Optimal Substructure）

大问题的最优解包含小问题的最优解

类比：你要写出最好的论文 → 每一章都要写得最好
数学：问题的最优解可以由子问题的最优解推导出来

2. 重叠子问题（Overlapping Subproblems）

不同的子问题会重复出现

类比：你要算很多人的年龄 → 发现很多人同一年出生，可以一起算
反面：分治法（如快速排序）的子问题不重叠

3. 状态转移方程（State Transition Equation）

描述子问题之间关系的公式

类比：菜谱：要做出红烧肉（当前状态），需要先准备好五花肉（上一个状态）
数学：dp[i] = max(dp[i-1] + value[i], value[i])

动态规划的两种实现方式

1. 自顶向下（Top-Down） + 备忘录

思路：从大问题开始，递归解决子问题，把结果记下来

# 斐波那契数列 - 自顶向下
def fib_top_down(n, memo={}):
    if n in memo:  # 已经算过了，直接返回
        return memo[n]
    
    if n <= 1:
        return n
    
    # 计算并存储
    memo[n] = fib_top_down(n-1, memo) + fib_top_down(n-2, memo)
    return memo[n]

# 调用
print(fib_top_down(50))  # 飞快！

优点：只计算需要的子问题
缺点：递归有栈溢出风险

2. 自底向上（Bottom-Up） + 表格

思路：从小问题开始，逐步构建到大问题

# 斐波那契数列 - 自底向上
def fib_bottom_up(n):
    if n <= 1:
        return n
    
    # 创建DP表
    dp = [0] * (n + 1)
    dp[1] = 1
    
    # 从小问题算到大问题
    for i in range(2, n + 1):
        dp[i] = dp[i-1] + dp[i-2]
    
    return dp[n]

# 调用
print(fib_bottom_up(50))  # 也非常快

优点：没有递归，效率高
缺点：可能计算不需要的子问题

经典动态规划问题详解

问题1：爬楼梯问题

题目：爬n阶楼梯，每次可以爬1阶或2阶，有多少种不同的方法？

分析：

要爬到第n阶，可以从第n-1阶爬1步，或者从第n-2阶爬2步
所以：f(n) = f(n-1) + f(n-2)

def climb_stairs(n):
    if n <= 2:
        return n
    
    # dp[i]表示爬到第i阶的方法数
    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]

# 示例
print(f"爬10阶楼梯有{climb_stairs(10)}种方法")  # 89种

问题2：最大子数组和

题目：给定数组[-2,1,-3,4,-1,2,1,-5,4]，找和最大的连续子数组

分析：

dp[i]表示以第i个元素结尾的最大子数组和
要么自己单独成组，要么加上前面的
状态转移：dp[i] = max(nums[i], dp[i-1] + nums[i])

def max_subarray(nums):
    if not nums:
        return 0
    
    n = len(nums)
    dp = [0] * n
    dp[0] = nums[0]
    max_sum = dp[0]
    
    for i in range(1, n):
        # 要么从当前重新开始，要么接上之前的
        dp[i] = max(nums[i], dp[i-1] + nums[i])
        max_sum = max(max_sum, dp[i])
    
    return max_sum

# 示例
nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
print(f"最大子数组和为：{max_subarray(nums)}")  # 6 [4,-1,2,1]

问题3：0-1背包问题

题目：背包容量W=10，物品重量和价值如下，求最大价值

物品	重量	价值
1	3	5
2	4	8
3	2	3
4	5	6

分析：

dp[i][j]表示考虑前i个物品，容量为j时的最大价值
对每个物品：要么不拿，要么拿（如果放得下）

def knapsack(weights, values, capacity):
    n = len(weights)
    # 创建DP表
    dp = [[0] * (capacity + 1) for _ in range(n + 1)]
    
    for i in range(1, n + 1):
        for w in range(1, capacity + 1):
            if weights[i-1] <= w:  # 当前物品可以放进去
                # 不拿 vs 拿
                dp[i][w] = max(
                    dp[i-1][w],  # 不拿
                    dp[i-1][w - weights[i-1]] + values[i-1]  # 拿
                )
            else:
                dp[i][w] = dp[i-1][w]  # 放不下，只能不拿
    
    return dp[n][capacity]

# 示例
weights = [3, 4, 2, 5]
values = [5, 8, 3, 6]
capacity = 10
print(f"最大价值为：{knapsack(weights, values, capacity)}")  # 17

问题4：最长公共子序列

题目：找"ABCD"和"ACDF"的最长公共子序列

分析：

dp[i][j]表示第一个字符串前i个和第二个前j个的最长公共子序列长度
如果字符相等：dp[i][j] = dp[i-1][j-1] + 1
如果不相等：dp[i][j] = max(dp[i-1][j], dp[i][j-1])

def longest_common_subsequence(text1, text2):
    m, n = len(text1), len(text2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if text1[i-1] == text2[j-1]:
                dp[i][j] = dp[i-1][j-1] + 1
            else:
                dp[i][j] = max(dp[i-1][j], dp[i][j-1])
    
    return dp[m][n]

# 示例
print(f"最长公共子序列长度：{longest_common_subsequence('ABCD', 'ACDF')}")  # 3 (ACD)

动态规划的进阶技巧

1. 状态压缩

当只需要上一行的信息时，可以用一维数组代替二维

# 背包问题的空间优化
def knapsack_optimized(weights, values, capacity):
    n = len(weights)
    dp = [0] * (capacity + 1)
    
    for i in range(n):
        # 从后往前遍历，避免覆盖需要的数据
        for w in range(capacity, weights[i] - 1, -1):
            dp[w] = max(dp[w], dp[w - weights[i]] + values[i])
    
    return dp[capacity]

2. 滚动数组

交替使用两个数组，节省空间

# 斐波那契的空间优化
def fib_optimized(n):
    if n <= 1:
        return n
    
    prev2, prev1 = 0, 1
    for i in range(2, n + 1):
        curr = prev1 + prev2
        prev2, prev1 = prev1, curr
    
    return prev1v

3. 记忆化搜索

对于复杂的递归结构，用字典缓存结果

from functools import lru_cache

@lru_cache(maxsize=None)
def fib_memoized(n):
    if n <= 1:
        return n
    return fib_memoized(n-1) + fib_memoized(n-2)

动态规划 vs 其他算法

算法	核心思想	适用场景	优缺点
动态规划	分解+记忆	最优子结构+重叠子问题	高效但难设计
分治法	分解+合并	子问题独立	简单但不记忆
贪心算法	局部最优	具有贪心选择性	快但不保证最优
回溯法	暴力尝试	需要所有解	保证正确但慢

动态规划解题五步法

步骤1：定义状态

问自己：dp[i]表示什么？
例子：dp[i]表示爬到第i阶的方法数

步骤2：找状态转移方程

问自己：当前状态和前面状态有什么关系？
例子：dp[i] = dp[i-1] + dp[i-2]

步骤3：确定初始条件

问自己：最小的子问题是什么？
例子：dp[0]=1, dp[1]=1

步骤4：确定计算顺序

问自己：从小问题到大问题怎么推？
例子：从i=2开始循环到n

步骤5：优化空间（可选）

问自己：能不能用更少的内存？
例子：只用两个变量代替数组

实战案例：编辑距离

题目：把"horse"变成"ros"最少需要几步？允许：插入、删除、替换

def edit_distance(word1, word2):
    m, n = len(word1), len(word2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    
    # 初始化边界
    for i in range(m + 1):
        dp[i][0] = i  # 删除所有字符
    for j in range(n + 1):
        dp[0][j] = j  # 插入所有字符
    
    # 填充DP表
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if word1[i-1] == word2[j-1]:
                dp[i][j] = dp[i-1][j-1]  # 字符相同，不需要操作
            else:
                dp[i][j] = min(
                    dp[i-1][j],      # 删除
                    dp[i][j-1],      # 插入
                    dp[i-1][j-1]     # 替换
                ) + 1
    
    return dp[m][n]

# 示例
print(f"编辑距离：{edit_distance('horse', 'ros')}")  # 3