题目描述

给你两个字符串 A 和 B，比如A = "ABCABBA"，B = "CBABAC"。

想象一个棋盘，横轴是 A 的字符，纵轴是 B 的字符。从左上角(0, 0)走到右下角(m, n)，每次只能往右、往下，或者斜着往右下走。

• 往右走：消耗 B 的一个字符，代价 1。
• 往下走：消耗 A 的一个字符，代价 1。
• 斜着走：只有当前两个字符相同才能走，代价 1，但一下搞定两个方向。

问题是：从起点到终点的最短距离是多少？

讲个故事：小明的最短通勤路

小明住在(0, 0)，公司在(m, n)。他有三条路可以选：

• 平路：往东走一格，或者往南走一格，各花 1 块钱。
• 捷径：如果路口招牌一样，可以走对角线，花 1 块钱但等于同时走了东和南。

小明当然想多走捷径。

能走多少条捷径？取决于 A 和 B 里有多少字符能按顺序对上。这就是最长公共子序列。

核心原理：为什么答案是 m + n - LCS？

这道题看着像在网格里找路，其实就是**最长公共子序列（LCS）**的换皮题。答案等于len(A) + len(B) - LCS(A, B)。

假设我们找到了一条最长公共子序列，长度为L。

• 这 L 个字符可以走斜边，花 L 块钱。
• A 还剩下m - L个字符，必须往下走，花m - L块钱。
• B 还剩下n - L个字符，必须往右走，花n - L块钱。

总花费 =L + (m - L) + (n - L) = m + n - L。

所以只要求出 LCS 长度，答案就出来了。

拿样例验证一下：A = "ABCABBA"长度 7，B = "CBABAC"长度 6，LCS 长度是 4（比如 “BABA” 或者 “CABA”）。最短距离就是7 + 6 - 4 = 9，和题目给的结果一致。

怎么求 LCS？

用动态规划。设dp[i][j]表示A[0..i-1]和B[0..j-1]的最长公共子序列长度。

转移方程：

• 如果A[i-1] == B[j-1]：dp[i][j] = dp[i-1][j-1] + 1
• 否则：dp[i][j] = max(dp[i-1][j], dp[i][j-1])

初始化：dp[0][j] = 0，dp[i][0] = 0。

代码实现

C 语言

#include<stdio.h>#include<stdlib.h>#include<string.h>intminPath(char*A,char*B){intm=strlen(A),n=strlen(B);int**dp=(int**)malloc((m+1)*sizeof(int*));for(inti=0;i<=m;i++){dp[i]=(int*)calloc(n+1,sizeof(int));}for(inti=1;i<=m;i++){for(intj=1;j<=n;j++){if(A[i-1]==B[j-1]){dp[i][j]=dp[i-1][j-1]+1;}else{dp[i][j]=dp[i-1][j]>dp[i][j-1]?dp[i-1][j]:dp[i][j-1];}}}intresult=m+n-dp[m][n];for(inti=0;i<=m;i++)free(dp[i]);free(dp);returnresult;}intmain(){charA[10005],B[10005];scanf("%s %s",A,B);printf("%d\n",minPath(A,B));return0;}

C++

#include<bits/stdc++.h>usingnamespacestd;intminPath(conststring&A,conststring&B){intm=A.size(),n=B.size();vector<vector<int>>dp(m+1,vector<int>(n+1,0));for(inti=1;i<=m;i++){for(intj=1;j<=n;j++){if(A[i-1]==B[j-1]){dp[i][j]=dp[i-1][j-1]+1;}else{dp[i][j]=max(dp[i-1][j],dp[i][j-1]);}}}returnm+n-dp[m][n];}intmain(){string A,B;cin>>A>>B;cout<<minPath(A,B)<<endl;return0;}

Java

importjava.util.Scanner;publicclassMain{publicstaticintminPath(StringA,StringB){intm=A.length(),n=B.length();int[][]dp=newint[m+1][n+1];for(inti=1;i<=m;i++){for(intj=1;j<=n;j++){if(A.charAt(i-1)==B.charAt(j-1)){dp[i][j]=dp[i-1][j-1]+1;}else{dp[i][j]=Math.max(dp[i-1][j],dp[i][j-1]);}}}returnm+n-dp[m][n];}publicstaticvoidmain(String[]args){Scannersc=newScanner(System.in);StringA=sc.next();StringB=sc.next();System.out.println(minPath(A,B));}}

JavaScript

functionminPath(A,B){constm=A.length,n=B.length;constdp=Array.from({length:m+1},()=>newArray(n+1).fill(0));for(leti=1;i<=m;i++){for(letj=1;j<=n;j++){if(A[i-1]===B[j-1]){dp[i][j]=dp[i-1][j-1]+1;}else{dp[i][j]=Math.max(dp[i-1][j],dp[i][j-1]);}}}returnm+n-dp[m][n];}// 输入处理constreadline=require('readline');constrl=readline.createInterface({input:process.stdin});rl.on('line',(line)=>{const[A,B]=line.trim().split(/\s+/);console.log(minPath(A,B));rl.close();});

Python

defmin_path(A,B):m,n=len(A),len(B)dp=[[0]*(n+1)for_inrange(m+1)]foriinrange(1,m+1):forjinrange(1,n+1):ifA[i-1]==B[j-1]:dp[i][j]=dp[i-1][j-1]+1else:dp[i][j]=max(dp[i-1][j],dp[i][j-1])returnm+n-dp[m][n]A,B=input().split()print(min_path(A,B))

空间优化（进阶）

如果你发现内存不够，可以用滚动数组把空间复杂度压到O(min(m, n))。

defmin_path_optimized(A,B):iflen(A)<len(B):A,B=B,A m,n=len(A),len(B)prev=[0]*(n+1)curr=[0]*(n+1)foriinrange(1,m+1):forjinrange(1,n+1):ifA[i-1]==B[j-1]:curr[j]=prev[j-1]+1else:curr[j]=max(prev[j],curr[j-1])prev,curr=curr,prevreturnm+n-prev[n]

复杂度分析

• 时间复杂度：O(m * n)
• 空间复杂度：O(m * n)，滚动数组优化后是O(min(m, n))

总结一下

这道题的关键不是背网格图，而是看出：

• 斜边 = 公共子序列里的一个字符
• 最短路径 = 总长度 - 最长公共子序列长度

下次看到"字符串网格"“最短路径”"匹配"这类关键词，脑子里先蹦出 LCS。

你平时做 OD 题最怕哪种题型？欢迎在评论区聊聊。