主題
題目連結：
題目意譯：
給定兩個字串 s 和 t，回傳 s 之中與 t 相等的相異子序列之數量。
一個字串的子序列為一個新的字串藉由刪除原始字串中的一些（可能沒有）字元且不更動剩下的字元之相對順序而產生（例，"ACE" 為 "ABCDE" 的一個子序列，而 "AEC" 則不是）。
保證答案可以存於一個 32 位元有號整數中。
限制：
1 ≦ s.length 、 t.length ≦ 1000
s 和 t 由英文字母組成。
範例測資：
範例 1：
輸入： s = "rabbbit", t = "rabbit"
輸出： 3
解釋：
如下所示，有 3 個方式你可以從 S 中生成 "rabbit"。
rabbbit
rabbbit
rabbbit
範例 2：
輸入： s = "babgbag", t = "bag"
輸出： 5
解釋：
如下所示，有 5 個方式你可以從 S 中生成 "bag"。
babgbag
babgbag
babgbag
babgbag
babgbag
解題思維：
（方便起見，以下字串的索引值從 1 開始）
定義一個二維陣列 D，其中 D[i][j] 代表 s 的子字串 s[1] ～ s[i]（i = 0 時，代表為空字串）有多少子序列等於 t 的子字串 t[1] ～ t[j]（j = 0 時，代表為空字串）。
因此我們可以看到初始條件為 D[i][0] = 1（對於任意 i 值），因為不管 s 內容為何其必定有一個子序列為空字串；且 D[0][j] = 0（對於 j ≧ 1），因為此時 s 為空但 t 為非空， s 不可能有除了空字串以外的子序列。
同時也可以看到遞迴式為：
當 s[i] ≠ t[j]，則 D[i][j] = D[i-1][j]。因為如果 s[i] 不與 t[j] 相同，則我們便不可能將 s[i] 配對到 t[j]，也就是說 s[i] 將毫無用處。因此我們只需考慮 s[1] ～ s[i - 1] 即可。
當 s[i] = t[j]，則 D[i][j] = D[i-1][j] + D[i-1][j-1]。與上不同，現在對於 t[j] 我們有兩種方案：一種是用 s[i] 與其相配，因此該方案子序列數將會是 D[i-1][j-1]、另一種則是同上的作法，將 s[i] 捨棄只考慮 s[1] ～ s[i - 1]，所以此方案會有 D[i-1][j] 個子序列。
而所求將位於 D[s.length][t.length]。
以範例 2 的輸入 s = "babgbag" 、 t = "bag" 為例，我們設立好初始條件後從下圖紅色數字群左上角出發由左至右、從上到下便可以求得整個二維陣列 D 之值：
可以看到最後所求位於最右下角（D[7][3]），其值為 5。
而其他的例子也是同理。不過雖然答案有保證會位於 32 位元有號整數中，但是不代表其他位置將都會可以存於其中。因此需要小心溢位。
此次分享到此為止，如有任何更加簡潔的想法或是有說明不清楚之地方，也煩請各位大大撥冗討論。
