题目描述给你两个字符串 A 和 B比如A ABCABBAB 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长度 7B CBABAC长度 6LCS 长度是 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] 0dp[i][0] 0。代码实现C 语言#includestdio.h#includestdlib.h#includestring.hintminPath(char*A,char*B){intmstrlen(A),nstrlen(B);int**dp(int**)malloc((m1)*sizeof(int*));for(inti0;im;i){dp[i](int*)calloc(n1,sizeof(int));}for(inti1;im;i){for(intj1;jn;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];}}}intresultmn-dp[m][n];for(inti0;im;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#includebits/stdc.husingnamespacestd;intminPath(conststringA,conststringB){intmA.size(),nB.size();vectorvectorintdp(m1,vectorint(n1,0));for(inti1;im;i){for(intj1;jn;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]);}}}returnmn-dp[m][n];}intmain(){string A,B;cinAB;coutminPath(A,B)endl;return0;}Javaimportjava.util.Scanner;publicclassMain{publicstaticintminPath(StringA,StringB){intmA.length(),nB.length();int[][]dpnewint[m1][n1];for(inti1;im;i){for(intj1;jn;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]);}}}returnmn-dp[m][n];}publicstaticvoidmain(String[]args){ScannerscnewScanner(System.in);StringAsc.next();StringBsc.next();System.out.println(minPath(A,B));}}JavaScriptfunctionminPath(A,B){constmA.length,nB.length;constdpArray.from({length:m1},()newArray(n1).fill(0));for(leti1;im;i){for(letj1;jn;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]);}}}returnmn-dp[m][n];}// 输入处理constreadlinerequire(readline);constrlreadline.createInterface({input:process.stdin});rl.on(line,(line){const[A,B]line.trim().split(/\s/);console.log(minPath(A,B));rl.close();});Pythondefmin_path(A,B):m,nlen(A),len(B)dp[[0]*(n1)for_inrange(m1)]foriinrange(1,m1):forjinrange(1,n1):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])returnmn-dp[m][n]A,Binput().split()print(min_path(A,B))空间优化进阶如果你发现内存不够可以用滚动数组把空间复杂度压到O(min(m, n))。defmin_path_optimized(A,B):iflen(A)len(B):A,BB,A m,nlen(A),len(B)prev[0]*(n1)curr[0]*(n1)foriinrange(1,m1):forjinrange(1,n1):ifA[i-1]B[j-1]:curr[j]prev[j-1]1else:curr[j]max(prev[j],curr[j-1])prev,currcurr,prevreturnmn-prev[n]复杂度分析时间复杂度O(m * n)空间复杂度O(m * n)滚动数组优化后是O(min(m, n))总结一下这道题的关键不是背网格图而是看出斜边 公共子序列里的一个字符最短路径 总长度 - 最长公共子序列长度下次看到字符串网格“最短路径”匹配这类关键词脑子里先蹦出 LCS。你平时做 OD 题最怕哪种题型欢迎在评论区聊聊。