Leetcode 115 - Distinct Subsequences（dp）

2019-11-14 09:57:15

字體：大中小

來源：轉載

供稿：網友

題意

給定兩個字符串S和T，要求刪除S中的某些字母使其成為T，問方案數。

思路

編輯距離的變形問題。

狀態表示：

我們記d[i,j] $d[i, j]$ ，從S[0, i]轉換到T[0, j]的方案數。

轉移方程：

Si==Tj $S_i == T_j$ ：即當前位置不用考慮，或者刪除Si $S_i$ 再考慮，即：d[i,j]=d[i?1,j?1]+d[i?1,j] $d[i, j] = d[i - 1, j - 1] + d[i - 1, j]$ Si≠Tj $S_i /neq T_j$ ：我們必須刪除Si $S_i$ 才可能將S轉變成T，即d[i,j]=d[i?1,j] $d[i, j] = d[i - 1, j]$

邊界條件：

d[0,0]=(S0==T0?1:0) $d[0, 0] = (S_0 == T_0 ? 1 : 0)$ 若i<j $i < j$ ，則d[i,j]=0 $d[i , j] = 0$

細節

注意邊界

代碼

const int maxn = 100005;int d[2][maxn];class Solution {public: int numDistinct(string s, string t) { int n = s.length(), m = t.length(); if (m == 0) return 1; memset(d, 0, sizeof(d)); d[0][0] = (s[0] == t[0] ? 1 : 0); int tt = 0; for (int i = 1; i < n; i++, tt ^= 1) { for (int j = 0; j < m; j++) { if (i < j) { d[tt ^ 1][j] = 0; } else { if (s[i] == t[j]) d[tt ^ 1][j] = (j > 0 ? d[tt][j - 1] : 1)+ d[tt][j]; else d[tt ^ 1][j] = d[tt][j]; } if (i == n - 1 && j == m - 1) return d[tt ^ 1][j]; } } return d[0][0]; }};

上一篇：求先序排列

下一篇：設計模式簡介