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