九章演算法 | Google 面試題 : 不同的子序列 解法1

撰文 | JZ

專欄 | 九章演算法

題目描述

給出字元串S和字元串T，計算S的不同的子序列中T出現的個數。

子序列字元串是原始字元串通過刪除一些(或零個)產生的一個新的字元串，並且對剩下的字元的相對位置沒有影響。(比如，「ACE」是「ABCDE」的子序列字元串,而「AEC」不是)。

樣例

intput: S=「1234」，T=「」noutput: 1n

解題思路

1. 做題一般遵循的都是將大問題轉化為小問題來求解，並據此初步得到記錄每個問題的解的狀態，再根據得到的狀態及狀態之間的關係來確定演算法。

2. 我們可以將這個問題拆分成兩個子問題：

• A：S[size_s-1]不與T序列中的字元匹配，那麼這個問題的就變成：求得長度為size_s-1 的串 S 有多少個子序列含有序列 T ；
• B：若S[size_s-1] 與 T 序列中的字元匹配，那麼只能是與T[size_t-1]匹配。若S[size_s-1] 與 T[size_t-1]相等，則可以使之匹配，那麼這個問題的答案就變成：求得長度為size_s-1 的序列 S[0..size_s-2] 有多少個子序列含有序列 T[0..size_t-2]。這樣，我們就完美的將原問題劃分為兩個規模更小的子問題。

子問題拆分完成，自然也就得到表示每個問題的狀態：

f[i][j]：表示S[0..i-1]中有多少個子序列包含T[0..j-1]。

我們要求的答案即為：

f[size_s][size_t]n

它的子問題為:

A:f[size_s-1][size_t]nB:f[size_s-1][size_t-1] (如果S[size_s-1]==T[size_t-1])n

得到狀態轉移方程：

f[i][j]=f[i-1][j];

if(S[i-1]==T[j-1])

f[i][j]+=f[i-1][j-1]；

3. 初始化。

根據狀態轉移方程，我們可以發現這是一個動態規劃（dp）。現在還沒有確定的就是初始化了。

初始化也簡單，動態規劃都是由一系列到初始狀態遞推得到之後的狀態，那麼我們要初始化的對象就是那些不能分解成子問題，也就是無法由別的狀態遞推得到的狀態。對於這個問題而言，f[i][0] 即滿足初始化的條件。

初始化的時候，要結合題意與代碼進行考量，比如這道題，按照題意，f[i][0]的結果應該都是 1 ，而這也不影響代碼的正確性。但是，如果題意要求不考慮空字元串，那麼f[i][0]的結果就應該是0，而這又會使得代碼出現錯誤。遇到這種情況，一般都是初始化成使代碼正確的版本，即將f[i][0]的結果初始化為1，輸出答案的時候，再特判那些特殊情況，也就是根據代碼計算得出的結果不正確的，比如 f[i][0]。

參考代碼

面試官分析

這道題目這樣做還不能夠達到hire的程度，還需要繼續優化。 更多解法，還請期待下一次的解法二

LintCode相關練習題

Backpack-ii