阿竺 ·1. 前言
在上個章節中我們討論了最常見的一維數組以及對應一維狀態轉移方程的解決方案，但是動態規劃的難點在于很多情況下使用一維的狀態轉移方程并不能解決問題，需要使用二維甚至三維的轉移方程。多維方程的狀態轉移函數需要抽象不同對象，例如多個字符串或者數組之間的關系。
2. 最長公共子序列
面試官提問：給定兩個字符串，求解最長公共子序列。
題目解析：
求解最長公共子序列問題是來源于算法網站LeetCode的經典題目，題目鏈接：https://leetcode.com/problems/longest-common-subsequence/。
首先是明確子序列的定義，例如對于字符串imooc，那么im、imo、imc都是它的子序列，子序列可以連續也可以不連續，如果是連續出現的，例如字符串imoo，一般被叫做子序列串。
其次是明確公共子序列的定義，對于兩個字符串，如果包含相同的子序列，那么這個子序列就是兩個字符串的公共子序列，例如imooc和moocer的公共子序列就有m和mo等，所有公共子序列中最長的子序列就是最長公共子序列（Longest Common Subsequence）。
首先從定性的角度來看，如果兩個字符串中，一個字符串的長度為零，那么最長公共子序列長度一定為零。
其次從定量的角度分析這個問題，例如給定的兩個字符串分別是X={x1,x2,x3 ... xm} 和Y={y1,y2,y3 ... ym}，表示X字符串是通過x1、x2一直到xm個連續字符組成，Y字符串同理。求解動態規劃的通用方案是找到子問題的共性，字符串的子問題就是子字符串，我們假設X'={x1,x2,x3 ... xi} 和 Y'={y1,y2,y3 ... yi} 的最長公共子序列是L，其中i<m。那么按照遞歸就有兩種狀態轉移流程：
（1）如果xi=yi，也就是兩個字符串的子字符串的最后一個字符剛好相等，那么{L,x(i+1)}或者{L,y{i+1}}就是新的最長公共子序列；
（2）如果xi≠yi，也就是兩個字符串的子字符串的最后一個字符并不相等，那么問題就可以轉換為求下面兩種情況的最長公共子序列：
第一種情況：X'={x1,x2,x3 ... x(i-1)} ，Y'={y1,y2,y3 ... yi}的最長公共子序列，假設為L1；
第二種情況：X'={x1,x2,x3 ... xi} ，Y'={y1,y2,y3 ... y(i-1)}的最長公共子序列，假設為L2。
最終需要的結果就是L = max(L1，L2)。
我們用 Java 語言實現上面描述的算法，示例：
class Solution {
public int longestCommonSubsequence(String text1, String text2) {
int n = text1.length();
int m = text2.length();
int[][] dp = new int[n+1][m+1];
//設置dp方程初始值
for(int i = 0; i < n+1; i++){
for(int j = 0; j < m+1; j++){
if(i == 0 || j == 0){
dp[i][j] = 0;
}
}
}
//循環更新狀態
for(int i = 1; i < n+1; i++){
for(int j = 1; j < m+1; j++){
if(text1.charAt(i-1) == text2.charAt(j-1)){
//如果這個位置的字符相同，說明相對于dp[i-1][j-1]剛好長一個字符
dp[i][j] = 1 + dp[i-1][j-1];
} else{
// 否則采用公共長度最長的
dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);
}
}
}
//返回結果
return dp[n][m];
}
}
3. 小結
本章節介紹了動態規劃中最經典的最長公共子序列問題，相對于一維數組下的動態規劃，二維數組的動態規劃一般不能壓縮空間，即時間復雜度基本都是O（n^2）的級別。字符串和動態規劃結合的類似問題還有最長上升子序列、字符串的編輯距離等。候選人需要從小型數據案例開始分析狀態轉移的核心，問題一般都能迎刃而解。
2025 imooc.com All Rights Reserved |