算法培训课件

算法培训课件：系统掌握数据结构与算法核心第一章算法与数据结构导论课程核心内容算法的定义与重要性算法复杂度分析方法时间复杂度与空间复杂度Python语言优势及应用算法复杂度基础大O符号表示法用于描述算法的渐进时间复杂度,关注输入规模增长时的性能变化趋势O(1)-常数时间O(logn)-对数时间O(n)-线性时间O(n²)-平方时间递归关系分析通过递推关系式求解复杂度,常用主定理和递归树方法递归树可视化分析主定理应用场景分治算法复杂度经典对比案例斐波那契数列的两种实现方式递归版本:O(2ⁿ)指数级动态规划:O(n)线性级数据结构基础概念数据结构是组织和存储数据的方式,不同的数据结构适用于不同的场景。理解数据结构的本质,能帮助我们在实际开发中做出最优选择。抽象数据类型ADT定义了数据的逻辑结构和操作接口,隐藏了具体实现细节,是面向对象设计的基础线性结构元素之间存在一对一关系,如数组、链表、栈、队列等,数据按顺序排列非线性结构元素之间存在一对多或多对多关系,如树、图等,结构更复杂但表达能力更强Python内置结构数组与链表数组的特点数组是最基本的数据结构,元素在内存中连续存储,支持O(1)时间的随机访问。但插入和删除操作需要移动元素,时间复杂度为O(n)。链表的优势链表通过指针连接节点,插入和删除只需修改指针,时间复杂度O(1)。但访问元素需要从头遍历,时间复杂度O(n)。单链表:每个节点指向下一个节点双链表:节点同时指向前后节点,可双向遍历循环链表:尾节点指向头节点,形成环状代码演示:链表插入操作栈与队列1栈(Stack)后进先出(LIFO)的线性数据结构,像一摞盘子,只能从顶部添加或移除元素。典型应用场景:括号匹配检查函数调用栈表达式求值浏览器历史记录2队列(Queue)先进先出(FIFO)的线性数据结构,像排队买票,从队尾加入,从队首离开。典型应用场景:任务调度系统广度优先搜索消息队列打印任务管理3双端队列(Deque)两端都可以进行插入和删除操作的队列,结合了栈和队列的特点,应用更灵活。Python实现:fromcollectionsimportdequedq=deque([1,2,3])dq.append(4)#右端添加dq.appendleft(0)#左端添加哈希表与散列冲突解决哈希表是实现快速查找的关键数据结构,通过哈希函数将键映射到数组索引,实现O(1)平均时间复杂度的查找、插入和删除操作。哈希函数将任意大小的输入数据转换为固定大小的输出值,决定了元素在表中的存储位置散列冲突不同的键经过哈希函数后得到相同的索引值,这是不可避免的现象链地址法在每个数组位置维护一个链表,冲突的元素添加到对应链表中开放地址法当发生冲突时,按某种规则寻找下一个空闲位置进行存储Python字典底层实现Python的dict使用哈希表实现,采用开放地址法解决冲突。字典的键必须是可哈希的不可变对象,如字符串、数字、元组等。字典在Python3.6+保持插入顺序。面试典型题目两数之和(TwoSum)字符串中第一个不重复的字符最长连续序列LRU缓存机制实现字符串基础与匹配算法字符串操作基础字符串是最常见的数据类型之一,Python提供了丰富的字符串操作方法。字符串是不可变对象,任何修改都会创建新字符串。切片操作:s[start:end:step]拼接与重复:+和*常用方法:split,join,replace格式化:f-string,format字符串匹配算法朴素匹配算法逐个字符比对,时间复杂度O(m×n),简单但效率低。KMP算法核心思想利用已匹配的信息,避免重复比较。通过next数组记录模式串的前缀信息,失配时跳转而非从头开始。时间复杂度O(m+n)。KMP算法代码演示defget_next(pattern):next_arr=[0]*len(pattern)j=0foriinrange(1,len(pattern)):whilej>0andpattern[i]!=pattern[j]:j=next_arr[j-1]ifpattern[i]==pattern[j]:j+=1next_arr[i]=jreturnnext_arr排序算法基础排序是计算机科学中最基本的操作之一。理解各种排序算法的原理和特点,是算法学习的重要基础。冒泡排序重复遍历数组,比较相邻元素并交换,大元素逐渐"冒泡"到末尾时间复杂度:O(n²)稳定性:稳定选择排序每次从未排序部分选择最小元素,放到已排序部分末尾时间复杂度:O(n²)稳定性:不稳定插入排序将元素逐个插入到已排序序列的正确位置,类似整理扑克牌时间复杂度:O(n²)稳定性:稳定基础排序算法虽然效率不高,但实现简单,适合小规模数据。插入排序对于近乎有序的数据表现优异,在实际应用中有其价值。高级排序算法01归并排序(MergeSort)采用分治策略,将数组递归分解为小数组,排序后再合并。时间复杂度O(nlogn),空间复杂度O(n),是稳定排序算法的代表。02快速排序(QuickSort)选择基准元素,将数组划分为小于和大于基准的两部分,递归排序。平均时间复杂度O(nlogn),最坏O(n²),是实践中最常用的排序算法。03堆排序(HeapSort)利用堆这种数据结构,先建立最大堆,然后依次取出堆顶元素。时间复杂度O(nlogn),空间复杂度O(1),不稳定但原地排序。快速排序代码实现defquick_sort(arr):iflen(arr)<=1:returnarrpivot=arr[len(arr)//2]left=[xforxinarrifx<pivot]middle=[xforxinarrifx==pivot]right=[xforxinarrifx>pivot]returnquick_sort(left)+middle+quick_sort(right)归并排序代码实现defmerge_sort(arr):iflen(arr)<=1:returnarrmid=len(arr)//2left=merge_sort(arr[:mid])right=merge_sort(arr[mid:])returnmerge(left,right)树的基础知识树是一种非线性的层次结构,由节点和边组成。树的每个节点可以有零个或多个子节点,除根节点外每个节点都有唯一的父节点。二叉树定义每个节点最多有两个子节点的树结构,分为左子树和右子树。二叉树是最重要的树形结构。遍历方法前序(根-左-右)、中序(左-根-右)、后序(左-右-根)、层序(逐层访问)二叉搜索树左子树所有节点小于根节点,右子树所有节点大于根节点,支持高效的查找、插入、删除操作。二叉树遍历代码示例classTreeNode:def__init__(self,val=0,left=None,right=None):self.val=valself.left=leftself.right=rightdefinorder_traversal(root):ifnotroot:return[]returninorder_traversal(root.left)+[root.val]+inorder_traversal(root.right)堆与优先级队列堆的定义与性质堆是一种特殊的完全二叉树,满足堆性质:最大堆:父节点的值大于或等于子节点最小堆:父节点的值小于或等于子节点堆通常用数组实现,对于索引i的节点:左子节点:2i+1右子节点:2i+2父节点:(i-1)//2优先级队列基于堆实现,每次取出优先级最高(或最低)的元素,应用于任务调度、事件驱动系统等场景核心操作插入O(logn)、删除最值O(logn)、获取最值O(1)、堆化O(n)应用场景TopK问题、堆排序、中位数维护、Dijkstra最短路径算法Pythonheapq模块使用importheapq#创建最小堆heap=[]heapq.heappush(heap,3)heapq.heappush(heap,1)heapq.heappush(heap,5)#弹出最小元素min_val=heapq.heappop(heap)#返回1#获取最大的3个元素largest=heapq.nlargest(3,[1,5,2,8,3])图论基础图是由节点(顶点)和边组成的数据结构,用于表示事物之间的关系。图可以是有向或无向的,带权或不带权的。邻接矩阵使用二维数组表示图,matrix[i][j]表示节点i到节点j的边。优点是查询边的存在快速O(1),缺点是空间复杂度O(V²),适合稠密图。graph=[[0,1,1,0],[1,0,0,1],[1,0,0,1],[0,1,1,0]]邻接表使用字典或列表存储每个节点的邻居节点。空间复杂度O(V+E),适合稀疏图,是实际应用中最常用的表示方法。graph={'A':['B','C'],'B':['A','D'],'C':['A','D'],'D':['B','C']}深度优先搜索(DFS)沿着一条路径尽可能深入探索,直到无法继续时回溯。使用栈(或递归)实现,适合路径问题、连通性检测。广度优先搜索(BFS)逐层访问节点,先访问距离起点近的节点。使用队列实现,适合最短路径、层次遍历问题。基础算法设计思想枚举法穷举所有可能的解,从中找出满足条件的答案。简单直接但效率较低,适合规模较小的问题。递归策略将问题分解为规模更小的相同问题,通过解决子问题来解决原问题。注意递归终止条件和栈溢出风险。分治思想将问题分解为若干独立的子问题,递归求解后合并结果。典型应用:归并排序、快速排序、二分查找。贪心算法每步都做出当前看来最优的选择,希望最终得到全局最优解。不是所有问题都适用,需要证明贪心选择性质。这四种思想是算法设计的基石。枚举是最朴素的方法,递归提供了优雅的表达方式,分治将复杂问题简化,贪心则在特定条件下提供高效解法。贪心算法经典题目活动选择问题:选择最多不冲突的活动霍夫曼编码:构造最优前缀编码最小生成树:Prim算法和Kruskal算法找零钱问题:用最少硬币数找零动态规划入门动态规划(DP)是解决最优化问题的强大工具,通过保存子问题的解避免重复计算。核心思想是将问题分解为重叠的子问题,自底向上或自顶向下求解。识别DP问题问题具有最优子结构和重叠子问题性质定义状态确定用什么变量表示子问题,通常用dp数组状态转移方程找出当前状态与子状态的关系,这是DP的核心初始化与边界设置基础情况的值,确定计算顺序计算结果按照转移方程填充dp数组,得到最终答案经典问题:爬楼梯每次可以爬1级或2级台阶,问爬到第n级有多少种方法?状态定义:dp[i]表示爬到第i级的方法数状态转移:dp[i]=dp[i-1]+dp[i-2]defclimb_stairs(n):ifn<=2:returnndp=[0]*(n+1)dp[1],dp[2]=1,2foriinrange(3,n+1):dp[i]=dp[i-1]+dp[i-2]returndp[n]经典问题:0-1背包有n个物品和容量为W的背包,第i个物品重量wi、价值vi,求最大价值。状态定义:dp[i][w]表示前i个物品、容量w时的最大价值状态转移:dp[i][w]=max(dp[i-1][w],#不选第i个dp[i-1][w-wi]+vi#选第i个)回溯算法回溯是一种通过探索所有可能的候选解来找出所有解的算法。如果候选解不符合要求,就回退到上一步继续尝试其他选择。回溯本质上是深度优先搜索的应用。选择在当前状态下,列出所有可能的选择路径约束判断选择是否满足问题的约束条件目标判断是否达到问题的目标状态回溯撤销上一步的选择,尝试其他路径八皇后问题在8×8棋盘上放置8个皇后,使得任意两个皇后都不在同一行、同一列或同一对角线上。回溯解法思路逐行放置皇后对于每一行,尝试每一列检查当前位置是否与已放置的皇后冲突如果不冲突,放置皇后并递归处理下一行如果冲突或后续无解,回溯到上一行尝试其他位置八皇后代码实现defsolve_n_queens(n):defbacktrack(row,cols,diag1,diag2):ifrow==n:result.append(cols[:])returnforcolinrange(n):d1,d2=row-col,row+colifcolincolsord1indiag1ord2indiag2:continuecols.add(col)diag1.add(d1)diag2.add(d2)backtrack(row+1,cols,diag1,diag2)cols.remove(col)diag1.remove(d1)diag2.remove(d2)

result=[]backtrack(0,set(),set(),set())returnresult剪枝优化技巧剪枝是提高回溯算法效率的关键。通过提前判断某条路径不可能产生解,避免继续探索,大幅减少搜索空间。常见的剪枝策略包括可行性剪枝、最优性剪枝和记忆化剪枝。算法设计进阶随机算法利用随机性来解决问题或提高算法效率。蒙特卡罗算法给出近似解,拉斯维加斯算法给出精确解但运行时间随机。典型应用包括快速排序的随机化、随机采样、概率验证等。复杂度理论初步P类问题:能在多项式时间内求解的问题NP类问题:解可以在多项式时间内验证的问题NP完全问题:最难的NP问题,如旅行商问题、图着色问题。如果任何一个NP完全问题有多项式解,则所有NP问题都有。算法正确性证明循环不变式:用于证明循环算法的正确性,需证明初始化、保持、终止三个性质数学归纳法:证明递归算法的常用方法,先证基础情况,再证递推关系反证法:假设算法错误,推导出矛盾,从而证明算法正确Python工程实践中的算法应用Python提供了丰富的标准库,充分利用这些工具可以大幅提升开发效率。理解内置数据结构和算法模块的实现原理,能帮助我们做出更好的技术选择。collections模块deque:双端队列,支持O(1)的两端操作Counter:计数器,快速统计元素频率defaultdict:带默认值的字典OrderedDict:保持插入顺序的字典namedtuple:具名元组,提高代码可读性heapq模块实现最小堆功能heappush/heappop操作nlargest/nsmallest查找merge合并有序序列适用于优先队列、TopK问题bisect模块二分查找算法insort维护有序列表bisect_left/right查找插入位置O(logn)时间复杂度适用于有序数据操作实际业务场景示例场景一:日志分析使用Counter统计关键词频率,heapq获取Top10高频词,时间复杂度O(nlogk)。场景二:缓存系统使用OrderedDict实现LRU缓存,O(1)时间访问和更新。代码优化示例fromcollectionsimportCounterimportheapq#高效统计TopKdeftop_k_frequent(words,k):count=Counter(words)returnheapq.nlargest(k,count.items(),key=lambdax:x[1])#使用bisect维护有序列表importbisectsorted_list=[1,3,5,7,9]bisect.insort(sorted_list,4)#[1,3,4,5,7,9]面试高频算法题解析(一)数组与链表专题两数之和(TwoSum)题目:给定数组和目标值,找出两个数使其和等于目标值思路:使用哈希表存储已遍历的数字和索引,O(n)时间解决deftwo_sum(nums,target):seen={}fori,numinenumerate(nums):complement=target-numifcomplementinseen:return[seen[complement],i]seen[num]=i时间复杂度:O(n)|空间复杂度:O(n)反转链表题目:反转一个单向链表思路:迭代或递归,改变指针方向。迭代法使用三个指针prev,curr,nextdefreverse_list(head):prev=Nonecurr=headwhilecurr:next_node=curr.nextcurr.next=prevprev=currcurr=next_nodereturnprev时间复杂度:O(n)|空间复杂度:O(1)合并两个有序数组题目:将两个有序数组合并为一个有序数组思路:从后向前填充,避免覆盖未处理的元素,充分利用已有空间时间复杂度:O(m+n)|空间复杂度:O(1)解题技巧总结:数组问题常用双指针、滑动窗口、哈希表;链表问题注意边界条件、善用快慢指针、虚拟头节点技巧。时刻思考时间和空间复杂度的权衡。面试高频算法题解析(二)栈、队列与哈希表专题1有效的括号使用栈匹配括号对。遇到左括号入栈,遇到右括号检查栈顶是否匹配。最后检查栈是否为空。2用队列实现栈使用两个队列,或者一个队列通过循环出入队实现。关键是理解LIFO和FIFO的转换。3LRU缓存机制结合哈希表和双向链表。哈希表提供O(1)查找,双向链表维护访问顺序,实现O(1)的get和put操作。4字母异位词分组将每个字符串排序后作为键,原字符串作为值存入哈希表。排序后相同的字符串属于同一组。LRU缓存代码框架fromcollectionsimportOrderedDictclassLRUCache:def__init__(self,capacity):self.cache=OrderedDict()self.capacity=capacity

defget(self,key):ifkeynotinself.cache:return-1self.cache.move_to_end(key)returnself.cache[key]

defput(self,key,value):ifkeyinself.cache:self.cache.move_to_end(key)self.cache[key]=valueiflen(self.cache)>self.capacity:self.cache.popitem(last=False)常见陷阱栈问题:忘记检查栈是否为空队列问题:循环队列的索引计算错误哈希表:没有处理键不存在的情况边界条件:空输入、单元素等特殊情况应对策略:先在纸上画出数据结构的变化过程,理清思路后再写代码。编写完成后用简单示例手动验证,特别注意边界情况。面试高频算法题解析(三)树与图专题1二叉树的最大深度递归求解:max(左子树深度,右子树深度)+1。也可用层序遍历计数层数。2验证二叉搜索树中序遍历结果应严格递增。或递归验证每个节点值在合法范围内。3二叉树的层序遍历使用队列BFS实现。每次处理一层的所有节点,记录层数或层内结果。4岛屿数量遍历矩阵,遇到陆地时计数器加1,并用DFS/BFS标记所有连通的陆地。5课程表(检测环)拓扑排序或DFS检测有向图中是否有环。维护访问状态,发现回边说明有环。岛屿数量代码实现defnum_islands(grid):ifnotgrid:return0

defdfs(i,j):if(i<0ori>=len(grid)orj<0orj>=len(grid[0])orgrid[i][j]!='1'):returngrid[i][j]='0'#标记为已访问dfs(i+1,j)dfs(i-1,j)dfs(i,j+1)dfs(i,j-1)

count=0foriinrange(len(grid)):forjinrange(len(grid[0])):ifgrid[i][j]=='1':count+=1dfs(i,j)returncount思路总结树问题关键点:明确递归的定义和返回值处理空节点的边界情况理解前中后序遍历的应用场景图问题关键点:选择合适的图表示方法防止重复访问(标记或集合)DFS用于路径/环检测,BFS用于最短路径面试高频算法题解析(四)动态规划与回溯专题爬楼梯dp[i]=dp[i-1]+dp[i-2],经典入门题打家劫舍不能抢相邻房屋,dp[i]=max(dp[i-1],dp[i-2]+nums[i])0-1背包二维dp或空间优化的一维dp,选或不选的决策零钱兑换完全背包变形,求最少硬币数或方案数最长递增子序列O(n²)的dp或O(nlogn)的贪心+二分编辑距离字符串DP经典题,三种操作的最小次数状态设计技巧明确状态含义:dp[i]或dp[i][j]代表什么找准决策点:每一步有哪些选择写出转移方程:当前状态如何由子状态得出确定边界条件:初始状态的值优化空间复杂度:滚动数组或状态压缩回溯题目精选全排列与组合子集问题电话号码的字母组合N皇后问题单词搜索性能优化要点记忆化搜索:自顶向下,缓存已计算的结果状态压缩:用位运算压缩状态空间剪枝优化:回溯中提前终止无效分支滚动数组:DP中只保留必要的前几行状态#最长递增子序列(贪心+二分,O(nlogn))deflength_of_lis(nums):tails=[]fornuminnums:left,right=0,len(tails)whileleft<right:mid=(left+right)//2iftails[mid]<num:left=mid+1else:right=midifleft==len(tails):tails.append(num)else:tails[left]=numreturnlen(tails)算法学习资源推荐经典教材算法导论(CLRS):算法圣经,理论严谨算法(第4版):Sedgewick著,工程实践导向算法图解:图文并茂,适合入门编程珠玑:问题解决思路和技巧在线刷题平台LeetCode:海量题库,分类详细,支持多语言牛客网:国内主流,模拟面试功能HackerRank:竞赛和认证Codeforces:算法竞赛平台可视化工具与社区VisuAlgo:算法动画演示,直观易懂AlgorithmVisualizer:开源可视化项目GitHub:学习优秀开源算法实现StackOverflow:问题讨论社区视频课程推荐MIT6.006算法导论普林斯顿算法课程(Coursera)GeeksforGeeks算法教程国内各大平台的算法专栏博客与公众号labuladong的算法小抄代码随想录五分钟学算法LeetCode官方题解算法学习方法与技巧高效刷题策略按专题分类练习,先易后难。每个专题练习20-30题形成肌肉记忆。不要贪多,重在理解和总结。定期复习已做过的题目,温故知新。做题流程建议仔细审题,明确输入输出和约束条件思考暴力解法,分析时间空间复杂度寻找优化方向,画图辅助思考编写代码前先写清楚思路注释实现代码,注意边界条件测试用例验证,特别是边界情况总结题目类型和解题模板面试准备策略提前3-6个月系统准备。按公司常考题型分类练习,多做模拟面试。准备自我介绍和项目经历,能清晰表达技术方案。练习在白板或纸上写代码,锻炼思维表达能力。编码规范与测试变量命名有意义,代码逻辑清晰。添加必要注释说明思路。养成写单元测试的习惯。考虑异常输入和边界情况。代码review和重构提升代码质量。刷题建议时间分配思考时间:15-20分钟,想不出来就看题解编码时间:20-30分钟,完成基本实现测试时间:10分钟,验证边界情况总结时间:10分钟,记录解题思路和模板一道题完整做下来约1小时,重在质量而非数量!课程总结与学习路径规划基础知识数组、链表、栈、队列、哈希表等基本数据结构树形结构二叉树、BST、堆、字典树等及其遍历操作图算法图的表示、DFS/BFS、最短路径、拓扑排序排序搜索各类排序算法、二分查找及其变体应用高级技巧动态规划、贪心、回溯、分治等算法思想数学与逻辑位运算、数论、概率、组合数学等基础进阶学习建议初级阶段(1-3月)掌握基本数据结构学习基础算法思想刷简单难度题100+建立代码模板库中级阶段(4-6月)深入动态规划和图论刷中等难度题200+参与周赛提升速度整理错题和心得高级阶段(7月+)挑战困难题和竞赛研究算法优化技巧参与开源项目实践准备系统设计面试实战项目与竞赛推荐参与ACM/ICPC、GoogleCodeJam、LeetCode周赛等算法竞赛。实现经典算法库,如STL的部分容器和算法。开发算法可视化工具或在线判题系统。将算法应用到实际项目中,如推荐系统、路径规划、数据分析等。课程答疑与互动环节问:如何克服刷题的畏难情绪?答:从简单题开始建立信心,设定小目标逐步达成。遇到难题不要气馁,看题解学习也是进步。加入学习小组互相鼓励,分享解题心得。记住算法能力是练出来的,坚持就会看到成效。问:时间复杂度分析有什么快速方法?答:记住常见模式:单层循环O(n),嵌套循环O(n²),二分O(logn),递归看递归树深度和每层工作量。多数情况看最内层循环执行次数和递归深度。实在不确定就代入具体数字估算。问:动态规划状态定义总是想不出来怎么办?答:多做题积累经验,熟悉常见的状态定义套路。尝试从问题的最优子结构入手。可以先写暴力递归,再加记忆化,最后改成DP。看优秀题解学习状态设计思路,慢慢就能形成直觉。学员经验分享"坚持每天刷2-3题,3个月后明显感觉思路清晰了很多。现在看到题目能快速识别类型,套用对应模板。"——张同学,已拿到大厂offer"建议准备一个错题本,记录做错的题和当时没想到的优化点。定期回顾,避免重复犯错。"——李同学,算法竞赛获奖者交流学习小贴士加入算法学习群组,互相监督打卡参与周赛和月赛,检验学习效果在博客或公众号分享解题思路关注大佬的题解,学习不同思路遇到问题及时提问,不要闭门造车定期总结知识点,建立知识体系代码实战演示(一)链表操作现场编码让我们现场编写一个常见的链表操作:删除链表中的倒数第N个节点。这道题综合考察了链表操作、双指针技巧和边界处理。问题描述给定一个链表,删除链表的倒数第n个节点,并返回链表的头节点。要求只遍历一次链表。解题思路使用双指针技巧,快指针先走n步然后快慢指针同时移动,直到快指针到达末尾此时慢指针的下一个节点就是要删除的节点使用虚拟头节点简化边界处理完整代码实现classListNode:def__init__(self,val=0,next=None):self.val=valself.next=nextdefremove_nth_from_end(head,n):#创建虚拟头节点,简化边界情况dummy=ListNode(0)dummy.next=head

#初始化快慢指针fast=slow=dummy

#快指针先走n步for_inrange(n):fast=fast.next

#快慢指针同时移动whilefast.next:fast=fast.nextslow=slow.next

#删除目标节点slow.next=slow.next.next

returndummy.next#测试用例#输入:1->2->3->4->5,n=2#输出:1->2->3->5代码调试要点边界情况:删除头节点(n等于链表长度)空指针检查:确保fast.next不为空时才移动测试用例:单节点链表、n=1、n等于链表长度时间复杂度:O(L),L为链表长度,只遍历一次空间复杂度:O(1),只使用常数额外空间代码实战演示(二)动态规划经典题目实现我们来实现一个经典的动态规划问题:最长公共子序列(LCS)。这道题是序列DP的代表,在文本比对、版本控制等领域有广泛应用。01定义状态dp[i][j]表示text1的前i个字符和text2的前j个字符的最长公共子序列长度02状态转移如果text1[i-1]==text2[j-1]:dp[i][j]=dp[i-1][j-1]+1否则:dp[i][j]=max(dp[i-1][j],dp[i][j-1])03初始化dp[0][j]和dp[i][0]都为0,表示空串的LCS长度为004计算答案按行或按列填充dp表,最终答案在dp[m][n]代码实现deflongest_common_subsequence(text1,text2):m,n=len(text1),len(text2)

#创建dp表dp=[[0]*(n+1)for_inrange(m+1)]

#填充dp表foriinrange(1,m+1):forjinrange(1,n+1):iftext1[i-1]==text2[j-1]:#字符相同,长度加1dp[i][j]=dp[i-1][j-1]+1else:#字符不同,取左或上的最大值dp[i][j]=max(dp[i-1][j],dp[i][j-1])

returndp[m][n]#测试text1="abcde"text2="ace"print(longest_common_subsequence(text1,text2))