蓝桥杯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])