Leetcode 115 - Distinct Subsequences（dp）

题意

给定两个字符串S和T，要求删除S中的某些字母使其成为T，问方案数。

思路

编辑距离的变形问题。

状态表示：

我们记 d[i,j] ，从S[0, i]转换到T[0, j]的方案数。

转移方程：

Si==Tj ：即当前位置不用考虑，或者删除 Si 再考虑，即： d[i,j]=d[i−1,j−1]+d[i−1,j] Si≠Tj ：我们必须删除 Si 才可能将S转变成T，即 d[i,j]=d[i−1,j]

边界条件：

d[0,0]=(S0==T0?1:0) 若 i<j ，则 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]; } };