蓝桥杯Python赛道备赛——Day7：动态规划（基础）
本博客就蓝桥杯中所涉及的动态规划基础问题进行讲解，包括：递推、记忆化搜索、最长公共子序列（LCS）和最长上升子序列（LIS）。
每一种动态规划问题都在给出定义的同时，给出了其求解方法的示例代码，以供低年级师弟师妹们学习和练习。
前序知识：
（1）Python基础语法
动态规划（基础）
- 一、递推（迭代法）
- 二、记忆化搜索（递归+缓存）
- 三、最长公共子序列（LCS）
- 四、最长上升子序列（LIS）
一、递推（迭代法）
-
定义：通过已知子问题的解逐步推导出更大问题的解，避免重复计算。
-
适用问题：具有明确递推公式的问题（如斐波那契数列）。
-
算法原理：
- 确定基础情况
- 建立状态转移方程
- 自底向上迭代计算
-
示例代码：
# 递推
# 实现斐波那契数列
def fib(n):
dp = [0] * (n+1) # 创建一个数组，大小为n+1
dp[1] = 1 # 初始条件，第一个斐波那契数为1
for i in range(2, n+1):
dp[i] = dp[i-1] + dp[i-2] # 当前的数等于前两个数之和
return dp[n] # 返回第n个斐波那契数
# 测试
print(fib(10)) # 输出第10个斐波那契数
二、记忆化搜索（递归+缓存）
-
定义：通过缓存已计算结果优化递归算法。
-
适用问题：递归结构清晰但存在重复计算的问题。
-
算法原理：
- 创建缓存字典
- 递归前先查询缓存
- 计算结果存入缓存
-
示例代码：
# 记忆化搜索
# 实现斐波那契数列
def memo_fib(n, memo={}):
# 基础情况处理
if n <= 1:
return n
# 检查是否已计算过
if n not in memo:
# 递归计算并存储结果
memo[n] = memo_fib(n-1, memo) + memo_fib(n-2, memo)
return memo[n]
# 测试：获取第10个斐波那契数
print(memo_fib(10)) # 输出：55
三、最长公共子序列（LCS）
-
定义：两个序列共有的最长子序列（不要求连续）。
-
适用问题：DNA比对、文本相似度分析。
-
算法原理：
（1）创建二维DP表。
（2）状态转移方程：
- 当字符相等：dp[i][j] = dp[i-1][j-1] + 1
- 当字符不等：dp[i][j] = max(dp[i-1][j], dp[i][j-1]) -
示例代码：
# 最长公共子序列
def lcs(text1, text2):
m, n = len(text1), len(text2)
# 创建(m+1)x(n+1)的DP表（包含空字符串情况）
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]
# 测试用例
text_a = "ABCBDAB"
text_b = "BDCAB"
print(lcs(text_a, text_b)) # 输出：4（对应"BCAB"或"BDAB"）
四、最长上升子序列（LIS）
-
定义：序列中数值严格递增的最长子序列。
-
适用问题：股票趋势分析、课程安排。
-
算法原理：
（1）维护每个位置的最长上升序列长度。
（2）状态转移方程：
dp[i] = max(dp[j]+1) 当nums[j] < nums[i]（j < i） -
示例代码：
# 最长递增子序列
def length_of_lis(nums):
if not nums:
return 0
n = len(nums)
dp = [1] * n # 每个元素自身构成长度为1的序列
for i in range(n):
# 检查前面所有可能形成上升序列的位置
for j in range(i):
if nums[j] < nums[i]:
dp[i] = max(dp[i], dp[j]+1)
return max(dp)
# 测试用例
nums = [10,9,2,5,3,7,101,18]
print(length_of_lis(nums)) # 输出：4（对应[2,5,7,101]）