§07 动态规划

动态规划 · 最长公共子序列 LCS

逐格比较两个字符串的字符，相等斜走 +1、不等取上左较大值；完成时回溯箭头标出 LCS 路径。

最长公共子序列 LCS

第 01 / 51 步

LCS：A = "ABCBDAB"，B = "BDCABA"。行 = A 的字符，列 = B 的字符，格子 = 前缀 LCS 长度。比较 0 · 交换 0

伪代码


				
					
					1
					// LCS：dp[i][j] = A[1..i] 与 B[1..j] 的 LCS 长度
				
			
				
					
					2
					for i = 1 to |A|:
				
			
				
					
					3
					  for j = 1 to |B|:
				
			
				
					
					4
					    if A[i] == B[j]: dp[i][j] = dp[i-1][j-1] + 1
				
			
				
					
					5
					    else: dp[i][j] = max(dp[i-1][j], dp[i][j-1])
				
			
				
					
					6
					  end for
				
			
				
					
					7
					end for
				
			
				
					
					8
					回溯：从右下角沿箭头走到左上角，斜走处即 LCS 字符

01 / 51

速度