【題目描述】
Given a stringSand a stringT, count the number of distinct subsequences ofTinS.
A subsequence of a string is a new string which is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (ie,"ACE"is a subsequence of"ABCDE"while"AEC"is not).
給出字符串S和字符串T军援，計算S的不同的子序列中T出現(xiàn)的個數(shù)敬辣。
子序列字符串是原始字符串通過刪除一些(或零個)產(chǎn)生的一個新的字符串，并且對剩下的字符的相對位置沒有影響帆阳。(比如橱夭，“ACE”是“ABCDE”的子序列字符串,而“AEC”不是)氨距。
【題目鏈接】
www.lintcode.com/en/problem/distinct-subsequences/
【題目解析】
這道題目是一道比較基礎(chǔ)的動態(tài)規(guī)劃題目，關(guān)鍵問題在理解題意和恰當?shù)脑O(shè)計狀態(tài)并列出狀態(tài)轉(zhuǎn)移方程棘劣。關(guān)于狀態(tài)的設(shè)立俏让，主要還是分析題目的步驟，規(guī)劃階段茬暇，然后將每個階段的結(jié)束視為一個狀態(tài)首昔，來進行設(shè)立。
對于這道題目糙俗，我們不妨設(shè)f(i, j)表示S長度為i的前綴和T長度為j的前綴形成的兩個字符串在這道題目下的答案是多少勒奇，即設(shè)S(i)表示S長度為i的前綴，T(j)表示T長度為j的前綴巧骚，則f(i, j)表示有多少個S(i)的子序列等價于T(j)赊颠。那么我們要求解的答案就可以用f(N, M)來表示，其中N是S的長度劈彪，M是T的長度竣蹦。
那么如何求解f(i, j)呢？這就要牽涉到狀態(tài)轉(zhuǎn)移方程沧奴。
我們的目標是將f(i, j)轉(zhuǎn)化為一個類似的子問題痘括，為了達成這種情況，一種思路枚舉與j匹配的最后一個字符，不放設(shè)為S的第k個字符（K<=i）纲菌，則有：
f(i, j) = sum(f(k - 1, j - 1)), 其中k滿足1<=k<=i,S[k]=T[j]
從而挠日，將f(i, j)轉(zhuǎn)化為了若干個規(guī)模變小（兩個參數(shù)都變泻采唷）的問題嚣潜，于是就可以列用這樣的狀態(tài)轉(zhuǎn)移方程進行求解：
按照i,j分別從小到大的順序，依次求解f(i, j)灶芝，這樣在求解時郑原，就可以確保其依賴的所有子問題都已經(jīng)得到了求解。
但是這樣還并沒有達到這道題目的最優(yōu)復(fù)雜度夜涕，不難發(fā)現(xiàn)，sum(f(k - 1, j - 1)), 1<=k
這樣一來属愤，狀態(tài)轉(zhuǎn)移的復(fù)雜度就縮減到了O(1)女器，加上狀態(tài)本身的O(NM)的復(fù)雜度，總共是O(NM)的復(fù)雜度住诸。
【參考答案】
