当前位置: 首页 > article >正文

蓝桥杯Python赛道备赛——Day7:动态规划(基础)

   本博客就蓝桥杯中所涉及的动态规划基础问题进行讲解,包括:递推、记忆化搜索、最长公共子序列(LCS)和最长上升子序列(LIS)。

   每一种动态规划问题都在给出定义的同时,给出了其求解方法的示例代码,以供低年级师弟师妹们学习和练习。

   前序知识:
(1)Python基础语法


动态规划(基础)

      • 一、递推(迭代法)
      • 二、记忆化搜索(递归+缓存)
      • 三、最长公共子序列(LCS)
      • 四、最长上升子序列(LIS)

一、递推(迭代法)

  1. 定义:通过已知子问题的解逐步推导出更大问题的解,避免重复计算。

  2. 适用问题:具有明确递推公式的问题(如斐波那契数列)。

  3. 算法原理:

    • 确定基础情况
    • 建立状态转移方程
    • 自底向上迭代计算
  4. 示例代码:

# 递推
# 实现斐波那契数列
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个斐波那契数

二、记忆化搜索(递归+缓存)

  1. 定义:通过缓存已计算结果优化递归算法。

  2. 适用问题:递归结构清晰但存在重复计算的问题。

  3. 算法原理:

    • 创建缓存字典
    • 递归前先查询缓存
    • 计算结果存入缓存
  4. 示例代码:

# 记忆化搜索
# 实现斐波那契数列
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)

  1. 定义:两个序列共有的最长子序列(不要求连续)。

  2. 适用问题:DNA比对、文本相似度分析。

  3. 算法原理:
    (1)创建二维DP表。
    (2)状态转移方程:
             - 当字符相等:dp[i][j] = dp[i-1][j-1] + 1
             - 当字符不等:dp[i][j] = max(dp[i-1][j], dp[i][j-1])

  4. 示例代码:

# 最长公共子序列
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. 适用问题:股票趋势分析、课程安排。

  3. 算法原理:
    (1)维护每个位置的最长上升序列长度。
    (2)状态转移方程:
             dp[i] = max(dp[j]+1) 当nums[j] < nums[i](j < i)

  4. 示例代码:

# 最长递增子序列
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])

http://www.kler.cn/a/590411.html

相关文章:

  • C++ map set pair
  • 《论分布式系统架构设计及其应用》架构师论文
  • Qt-QChart实现折线图
  • [贪心算法]-最大数(lambda 表达式的补充)
  • Java 集合框架(Collection)
  • QT:动态属性和对象树
  • Compose笔记(九)--Checkbox
  • [数据结构]排序之 快速排序详解(递归版非递归版)
  • 游戏引擎学习第162天
  • 2025年高职大数据可视化实训室建设及实训平台整体解决方案
  • Vue秘籍:如何动态修改页面 Title(浏览器页签名称)?
  • idea cpu干到100%的解决方法?
  • HarmonyOS NEXT开发实战——HUAWEI DevEco Studio 开发指南
  • 车载以太网测试-13【网络层-IGMP协议】
  • 【Godot】Viewpoint
  • mapbox基础,使用线类型geojson加载symbol符号图层,用于标注文字
  • 解锁智慧养老新可能,全面提升养老生活质量
  • Go语言中的错误处理与异常恢复:性能对比与实践思考
  • 【leetcode】51.N皇后
  • 如何检查CMS建站系统的插件是否安全?