算法设计与分析演讲稿中包含动态规划和最长公共子序列的C++实现

最长公共子串

• • 引言

    • 最长公共子序列

    • • 概述
      • 运行机制
      • • 1.蛮力法

    • 2.动态规划方法

      • 程序示例
      • 时间复杂度评估

---

前言

本篇文章旨在服务于算法设计与分析课程的教学需求，其内容以作业为导向进行编写，因此并不完全适用于自主学习。

最长公共子序列

介绍

简而言之，子串与子序列的核心差异在于，子串由连续的字符组成，而子序列中的字符可以是非连续的。在此，我引用他人的示意图以作进一步说明。

实现原理概述

1.暴力算法

若采用暴力算法，其基本思路是将str1中所有的潜在子序列逐一提取，随后在str2中进行匹配，若发现存在一致的子串，则将其记录下来。然而，只需稍加分析便可发现，这一方法存在明显的不合理之处。