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