动态规划算法python
从〈状态定义〉到〈最优子结构〉,用Python构建高效思维。本指南覆盖网民最常搜索的背包问题、最长递增子序列、编辑距离等,并提供可直接运行的代码片段。
⚙️ 为什么选择Python?
- 简洁语法快速验证状态转移方程
- 丰富的内置结构(列表、字典)实现记忆化
- 〈@lru_cache〉装饰器一行优化递归
※ 今日聚焦
【背包九讲】Python实现、区间DP模板、股票买卖系列。网友还关心:如何从暴力递归推导出动态规划。
⚡ 核心进阶 · 时间轴
〈状态〉与〈选择〉是动态规划的核心。定义dp[i]的含义往往决定解题方向。
〔 经典专题 〕选项卡详解
0/1背包 · Python实现
状态定义:dp[i][w] 表示前i个物品容量w的最大价值。转移方程:dp[i][w] = max(dp[i-1][w], dp[i-1][w-wt[i]]+val[i])。
def knapsack(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]
网友还关心:完全背包与多重背包的Python优化写法。
最长递增子序列 (LIS)
给定数组[10,9,2,5,3,7,101,18],输出4。使用dp[i]表示以i结尾的LIS长度。时间复杂度O(n²),二分优化至O(n log n)。
def lengthOfLIS(nums):
dp = [1]*len(nums)
for i in range(len(nums)):
for j in range(i):
if nums[i] > nums[j]:
dp[i] = max(dp[i], dp[j]+1)
return max(dp)
编辑距离 · 字符串转换
将word1转换成word2的最少操作数。〈插入〉〈删除〉〈替换〉各计一步。dp[i][j]表示前缀子串的最小编辑距离。
def minDistance(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]
硬币找零 · 最少硬币数
coins=[1,2,5], amount=11,输出3(5+5+1)。完全背包变种,dp[i]表示金额i所需最少硬币。
def coinChange(coins, amount):
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
「网友们还关心」热点聚焦
◤ 状态转移方程推导技巧
明确〈base case〉、〈选择〉、〈状态〉。例如打家劫舍问题:dp[i] = max(dp[i-1], dp[i-2]+nums[i])。
◤ Python记忆化递归模板
from functools import lru_cache 然后使用@lru_cache(None)装饰函数,自动缓存结果。
◤ 区间DP · 戳气球
定义dp[i][j]为开区间(i,j)最大硬币数。Python实现时注意边界处理。
◤ 股票买卖最佳时机
多维状态:dp[i][k][0/1]表示第i天交易k次是否持有。网友常搜“冷冻期”变种。
【高频问答】动态规划算法python
| 常见疑问 | 简明解答 |
|---|---|
| 如何判断一道题用DP? | 存在〈重叠子问题〉+〈最优子结构〉,求最值/计数/可行性。 |
| Python递归深度限制? | 使用sys.setrecursionlimit()或改用迭代递推。 |
| 二维DP如何降维? | 观察状态只依赖上一行,用一维数组倒序/正序更新。 |
| 记忆化搜索与递推区别? | 记忆化自顶向下,递推自底向上,时间复杂度相同。 |
ⅰ 网友还搜索:“动态规划python背包问题详解”“DP状态压缩技巧”。
※ 周边深度 · 动态规划与Python生态
⑶ 矩阵链乘法
给定矩阵序列,求最少乘法次数。dp[i][j] = min(dp[i][k]+dp[k+1][j]+p[i-1]p[k]p[j])。Python实现常用三层循环。
⑷ 正则表达式匹配
LeetCode 10:实现 '.' 和 '*' 的支持。dp[i][j]表示s前i个与p前j个匹配,需仔细处理*号。
〈§ 学习路径〉:递归树 → 记忆化 → 递推 → 空间优化。配合Python的简洁特性,快速验证思路。