本博客就蓝桥杯中所涉及的动态规划基础问题进行讲解，包括：递推、记忆化搜索、最长公共子序列（LCS）和最长上升子序列（LIS）。
每一种动态规划问题都在给出定义的同时，给出了其求解方法的示例代码，以供低年级师弟师妹们学习和练习。
前序知识：
（1）Python基础语法
动态规划（基础）
- 一、递推（迭代法）
- 二、记忆化搜索（递归+缓存）
- 三、最长公共子序列（LCS）
- 四、最长上升子序列（LIS）
一、递推（迭代法）
-
定义：通过已知子问题的解逐步推导出更大问题的解，避免重复计算。
-
适用问题：具有明确递推公式的问题（如斐波那契数列）。
-
算法原理：
- 确定基础情况
- 建立状态转移方程
- 自底向上迭代计算
-
示例代码：
python"># 递推
# 实现斐波那契数列
def fib(n):dp = [0] * (n+1) # 创建一个数组，大小为n+1dp[1] = 1 # 初始条件，第一个斐波那契数为1for i in range(2, n+1):dp[i] = dp[i-1] + dp[i-2] # 当前的数等于前两个数之和return dp[n] # 返回第n个斐波那契数# 测试
print(fib(10)) # 输出第10个斐波那契数二、记忆化搜索（递归+缓存）
-
定义：通过缓存已计算结果优化递归算法。
-
适用问题：递归结构清晰但存在重复计算的问题。
-
算法原理：
- 创建缓存字典
- 递归前先查询缓存
- 计算结果存入缓存
-
示例代码：
python"># 记忆化搜索
# 实现斐波那契数列
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]) -
示例代码：
python"># 最长公共子序列
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] + 1else: # 字符不匹配的情况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） -
示例代码：
python"># 最长递增子序列
def length_of_lis(nums):if not nums:return 0n = 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]）
