主題
題目連結(jié)：
題目意譯：
你被給定一個由相同長度的字串所組成之列表 words 以及一個字串 target。
你的任務(wù)是藉由給定的 words 以及下列規(guī)則來形成 target：
target 應(yīng)由左至右形成。
為了形成 target 的第 i 個字元（索引值從 0 開始），你可以在 words 中的第 j 個字串選出第 k 個字元，前提是 target[i] = words[j][k]。
一旦你使用了 words 中的第 j 個字串選出第 k 個字元，你不得再使用 words 中任意字串的第 x 字元，其中 x ≦ k。換句話說，所有字串中位於索引值 k 以及其左側(cè)所有字元都將不得使用。
重複此步驟直到你形成字串 target。
注意到只要你可以符合上述規(guī)則，你可以使用 words 中同一字串中的多個字元。
回傳從 words 形成 target 的方法數(shù)。由於答案可能很大，將其模 10 ^ 9 + 7 再回傳。
限制：
1 ≦ words.length ≦ 1000
1 ≦ words[i].length ≦ 1000
words 中所有字串長度相同。
1 ≦ target.length ≦ 1000
words[i] 和 target 只由小寫英文字母組成。
範例測資：
範例 1：
輸入： words = ["acca","bbbb","caca"], target = "aba"
輸出： 6
解釋： 有 6 種方式可以形成 target。
"aba" → 索引值 0 （"acca"） 、 索引值 1 （"bbbb"） 、 索引值 3 （"caca"）
"aba" → 索引值 0 （"acca"） 、 索引值 2 （"bbbb"） 、 索引值 3 （"caca"）
"aba" → 索引值 0 （"acca"） 、 索引值 1 （"bbbb"） 、 索引值 3 （"acca"）
"aba" → 索引值 0 （"acca"） 、 索引值 2 （"bbbb"） 、 索引值 3 （"acca"）
"aba" → 索引值 1 （"caca"） 、 索引值 2 （"bbbb"） 、 索引值 3 （"acca"）
"aba" → 索引值 1 （"caca"） 、 索引值 2 （"bbbb"） 、 索引值 3 （"caca"）
範例 2：
輸入： words = ["abba" 、"baab"] 、 target = "bab"
輸出： 4
解釋： 有 4 種方式可以形成 target。
"bab" → 索引值 0 （"baab"） 、 索引值 1 （"baab"） 、 索引值 2 （"abba"）
"bab" → 索引值 0 （"baab"） 、 索引值 1 （"baab"） 、 索引值 3 （"baab"）
"bab" → 索引值 0 （"baab"） 、 索引值 2 （"baab"） 、 索引值 3 （"baab"）
"bab" → 索引值 1 （"abba"） 、 索引值 2 （"baab"） 、 索引值 3 （"baab"）
解題思維：
如同前天所講的——如果不知道要做哪些子問題，那就全做！這就是動態(tài)規(guī)劃（Dynamic Programming，DP）的精神。
那我們會有哪些子問題？首先，我們隨便選一個索引值 i 來從 words 中某個字串選第 i 個字元與 target 中隨便選的第 j 個字元來配對。
根據(jù)題目的定義，此時我們將不能用 words 中任何字串的前 i 個字元來與 target[j]「後面」的字元相配。所以前 i 個字元此時只會跟 target 的前 j 個字元「有關(guān)」。而這就是我們的子問題。
定義一個二維陣列 D，其中 D[i][j] 代表著在已經(jīng)用所有字串的前 i 個字元來配對 target 前 j 個字元的情況下，要使用任意一個字串第 i 個字元來與 target 中第 j 個字元相配對的方法數(shù)。可以看到其遞迴式為：
如果 i < j，則 D[i][j] = 0；
（上式為遞迴停止條件。意涵很單純，字元不夠用的話，當然方法數(shù)為 0）
如果 i ≧ j，則 D[i][j] = S(target[j], i) × (D[i - 1][j - 1] + D[i - 2][j - 1] + …… D[0][j - 1])
其中 S(target[j], i) 代表著在 words 中所有字串有多少在索引值 i 的位置之字元恰好為 target[j]。而這可以事先掃過一次建表而得到。同時，後面那一個級數(shù)可以用前綴和（Prefix Sums）來快速求得（參見這題）。
最後所求即為 D[0][m - 1] + D[1][m - 1] + …… + D[n - 1][m - 1]，其中 n 為 words 中單一字串的長度、m 為 target 的長度。記得任何運算過程中要對 10 ^ 9 + 7 取餘數(shù)，以免溢位。
不過範例程式碼有將 D[i][j] 的維度 j 省略掉來使空間最佳化。有興趣的讀者可以思考或是參考看看如何省略。
此次分享到此為止，如有任何更加簡潔的想法或是有說明不清楚之地方，也煩請各位大大撥冗討論。
