上一篇
什么是动态规划？
动态规划（Dynamic Programming，简称DP）是一种解决复杂问题的算法设计技术，它通过将问题分解为相互重叠的子问题，并存储子问题的解来避免重复计算，从而提高算法效率。
动态规划的核心思想
- 最优子结构：问题的最优解包含其子问题的最优解
- 重叠子问题：问题可以分解为多个相同的子问题
- 状态转移方程：定义问题状态与子问题状态之间的关系
- 记忆化存储：存储子问题的解以避免重复计算
动态规划适用场景
- 最优化问题（求最大值、最小值）
- 计数问题（求方案总数）
- 可行性问题（判断问题是否有解）
- 子序列、子数组问题
- 背包问题、路径问题
动态规划实现步骤
- 定义状态：确定DP数组的含义（一维、二维或多维）
- 确定状态转移方程：找出DP[i]与之前状态的关系
- 初始化边界条件：设置DP数组的初始值
- 确定计算顺序：自底向上（迭代）或自顶向下（递归+记忆化）
- 返回最终结果：根据DP数组得出最终答案
- 空间优化（可选）：减少DP数组维度
通用动态规划框架
def dp_solution(params):
# 初始化DP数组
dp = [0] * (n + 1)
# 设置边界条件
dp[0] = initial_value
# 状态转移
for i in range(1, n + 1):
# 根据状态转移方程更新dp[i]
dp[i] = some_function(dp[j] for j in range(i))
# 返回最终结果
return dp[n]经典动态规划案例
🔢 斐波那契数列
计算第n个斐波那契数：F(0)=0, F(1)=1, F(n)=F(n-1)+F(n-2)
def fibonacci(n):
if n <= 1:
return n
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]
# 优化版本（空间O(1)）
def fib_optimized(n):
if n <= 1:
return n
a, b = 0, 1
for _ in range(2, n+1):
a, b = b, a+b
return b🎒 0-1背包问题
给定物品重量和价值，在容量限制下求最大价值
def knapSack(W, wt, val, n):
dp = [[0]*(W+1) for _ in range(n+1)]
for i in range(1, n+1):
for w in range(1, W+1):
if wt[i-1] <= w:
dp[i][w] = max(val[i-1] + dp[i-1][w-wt[i-1]],
dp[i-1][w])
else:
dp[i][w] = dp[i-1][w]
return dp[n][W]
# 优化版本（一维DP）
def knapSack_optimized(W, wt, val, n):
dp = [0]*(W+1)
for i in range(n):
for w in range(W, wt[i]-1, -1):
dp[w] = max(dp[w], val[i] + dp[w-wt[i]])
return dp[W]🔤 最长公共子序列
求两个字符串的最长公共子序列长度
def lcs(X, Y):
m, n = len(X), len(Y)
dp = [[0]*(n+1) for _ in range(m+1)]
for i in range(1, m+1):
for j in range(1, n+1):
if X[i-1] == Y[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]动态规划与其他算法对比
| 算法类型 | 时间复杂度 | 空间复杂度 | 适用场景 | 特点 |
|---|---|---|---|---|
| 动态规划 | 通常O(n²)或O(n*m) | 通常O(n)或O(n*m) | 有重叠子问题的最优化问题 | 高效但设计复杂，需要状态转移方程 |
| 分治算法 | 通常O(n log n) | O(log n)或O(n) | 子问题独立的问题 | 递归分解，无重叠子问题 |
| 贪心算法 | 通常O(n log n) | O(1) | 局部最优导致全局最优的问题 | 高效但不一定能得到最优解 |
| 暴力搜索 | 通常指数级 | O(n) | 小规模问题 | 简单但效率低 |
动态规划优化技巧
- 状态压缩：减少DP数组维度（如二维转一维）
- 滚动数组：只保留必要状态，减少空间使用
- 记忆化搜索：递归+缓存，避免重复计算
- 优化状态转移：使用数据结构（堆、单调队列）加速转移
- 问题转化：将问题转化为已知的DP模型
记忆化搜索示例（斐波那契数列）
def fib_memo(n, memo=None):
if memo is None:
memo = {}
if n in memo:
return memo[n]
if n <= 1:
return n
memo[n] = fib_memo(n-1, memo) + fib_memo(n-2, memo)
return memo[n]动态规划学习要点
📌
从经典问题入手：先掌握斐波那契数列、背包问题、最长公共子序列等经典DP问题
📌
理解状态设计：状态定义是DP的核心，决定了算法的正确性和效率
📌
多画状态转移表：通过表格可视化DP数组的变化过程
📌
循序渐进：先实现基础版本，再考虑空间优化等高级技巧
📌
大量练习：在LeetCode、Codeforces等平台刷题巩固
发表评论