动态规划
动态规划（Dynamic Programming，DP）是解决最优化问题的重要方法。它通过将问题分解为子问题，并存储子问题的解来避免重复计算，从而高效地解决问题。
动态规划基础
动态规划的特点
- 最优子结构：问题的最优解包含子问题的最优解
- 重叠子问题：子问题会被重复计算
- 状态转移方程：描述如何从子问题的解得到当前问题的解
动态规划的步骤
- 定义状态：dp[i] 或 dp[i][j] 表示什么
- 状态转移方程：如何从已知状态推导出当前状态
- 初始状态：边界条件的设置
- 计算顺序：确定计算状态的顺序
一维动态规划
1. 斐波那契数列
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]
# 空间优化
def fibonacci_optimized(n):
if n <= 1:
return n
prev2, prev1 = 0, 1
for i in range(2, n + 1):
current = prev1 + prev2
prev2, prev1 = prev1, current
return prev1
2. 爬楼梯
题目：每次可以爬 1 或 2 个台阶，爬到第 n 阶有多少种方法？
def climb_stairs(n):
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. 打家劫舍
题目：不能偷相邻的房子，求最大收益。
def rob(nums):
if not nums:
return 0
if len(nums) == 1:
return nums[0]
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. 最长递增子序列（LIS）
def length_of_lis(nums):
if not nums:
return 0
dp = [1] * len(nums)
for i in range(1, len(nums)):
for j in range(i):
if nums[j] < nums[i]:
dp[i] = max(dp[i], dp[j] + 1)
return max(dp)
二维动态规划
1. 不同路径
题目：从左上角到右下角，只能向右或向下移动，有多少种路径？
def unique_paths(m, n):
dp = [[1] * n for _ in range(m)]
for i in range(1, m):
for j in range(1, n):
dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
return dp[m - 1][n - 1]
# 空间优化
def unique_paths_optimized(m, n):
dp = [1] * n
for i in range(1, m):
for j in range(1, n):
dp[j] += dp[j - 1]
return dp[-1]
2. 最小路径和
题目：从左上角到右下角，路径上数字之和最小是多少？
def min_path_sum(grid):
m, n = len(grid), len(grid[0])
dp = [[0] * n for _ in range(m)]
dp[0][0] = grid[0][0]
# 第一行
for j in range(1, n):
dp[0][j] = dp[0][j - 1] + grid[0][j]
# 第一列
for i in range(1, m):
dp[i][0] = dp[i - 1][0] + grid[i][0]
# 其他位置
for i in range(1, m):
for j in range(1, n):
dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j]
return dp[m - 1][n - 1]
3. 最长公共子序列（LCS）
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]
4. 编辑距离
def min_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
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] = 1 + min(
dp[i - 1][j], # 删除
dp[i][j - 1], # 插入
dp[i - 1][j - 1] # 替换
)
return dp[m][n]
背包问题
1. 0-1 背包
题目：每个物品只能选一次，在容量限制下最大化价值。
def knapsack_01(weights, values, capacity):
n = len(weights)
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:
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]
# 空间优化
def knapsack_01_optimized(weights, values, capacity):
dp = [0] * (capacity + 1)
for i in range(len(weights)):
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 knapsack_unbounded(weights, values, capacity):
dp = [0] * (capacity + 1)
for w in range(1, capacity + 1):
for i in range(len(weights)):
if weights[i] <= w:
dp[w] = max(dp[w], dp[w - weights[i]] + values[i])
return dp[capacity]
区间动态规划
1. 最长回文子串
def longest_palindrome(s):
n = len(s)
dp = [[False] * n for _ in range(n)]
start, max_len = 0, 1
# 单个字符
for i in range(n):
dp[i][i] = True
# 两个字符
for i in range(n - 1):
if s[i] == s[i + 1]:
dp[i][i + 1] = True
start, max_len = i, 2
# 三个及以上字符
for length in range(3, n + 1):
for i in range(n - length + 1):
j = i + length - 1
if s[i] == s[j] and dp[i + 1][j - 1]:
dp[i][j] = True
start, max_len = i, length
return s[start:start + max_len]
2. 矩阵链乘法
def matrix_chain_order(p):
n = len(p) - 1
dp = [[0] * n for _ in range(n)]
for length in range(2, n + 1):
for i in range(n - length + 1):
j = i + length - 1
dp[i][j] = float('inf')
for k in range(i, j):
cost = dp[i][k] + dp[k + 1][j] + p[i] * p[k + 1] * p[j + 1]
dp[i][j] = min(dp[i][j], cost)
return dp[0][n - 1]
状态压缩动态规划
旅行商问题（TSP）
def tsp(dist):
n = len(dist)
dp = [[float('inf')] * n for _ in range(1 << n)]
dp[1][0] = 0
for mask in range(1, 1 << n):
for u in range(n):
if mask & (1 << u):
for v in range(n):
if not (mask & (1 << v)):
new_mask = mask | (1 << v)
dp[new_mask][v] = min(
dp[new_mask][v],
dp[mask][u] + dist[u][v]
)
result = float('inf')
for u in range(1, n):
result = min(result, dp[(1 << n) - 1][u] + dist[u][0])
return result
总结
动态规划是解决最优化问题的重要方法：
- 核心思想：最优子结构 + 重叠子问题
- 解题步骤：定义状态 → 状态转移 → 初始状态 → 计算顺序
- 常见类型：一维 DP、二维 DP、背包问题、区间 DP、状态压缩 DP
- 优化技巧：空间优化、滚动数组
掌握动态规划能够帮助你解决许多复杂的优化问题。
接下来，让我们学习贪心算法，这是另一种解决最优化问题的方法。