【一天一道LeetCode】#115. Distinct Subsequences

# 一天一道LeetCode

## （一）题目

Given a string S and a string T, count the number of distinct subsequences of T in S.

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).

Here is an example:
S = “rabbbit”, T = “rabbit”

Return 3.

## （二）解题

```class Solution {
public:
int numDistinct(string s, string t) {
if(s.length()==0||t.length()==0) return 0;
int num =0;
dpDistinct(s,t,0,0,num);
return num;
}
void dpDistinct(string& s, string& t , int i , int j,int& num)
{
if(j==t.length()){num++;return;}
if(s[i]==t[j])
{
//choose this words
if(i<s.length()&&j<t.length()) dpDistinct(s, t , i+1, j+1,num);
//not choose this words
if(i<s.length()) dpDistinct(s, t , i+1, j,num);
}
else
//Don't equal
if(i<s.length()) dpDistinct(s, t , i+1, j,num);
}
};```

dp a b b b c
1 1 1 1 1 1
a 0 1 1 1 1 1
b 0 0 1 2 3 3
c 0 0 0 0 0 3

```class Solution {
public:
int numDistinct(string s, string t) {
vector<vector<int>> dp;
for(int i = 0 ; i < t.length()+1;i++)
{
vector<int> temp(s.length()+1,0);
dp.push_back(temp);
}
for(int i = 0 ; i < s.length()+1;i++) dp[0][i]=1;//初始化dp
for(int i = 1 ; i < t.length()+1; i++)
{
for(int j = 1 ; j < s.length()+1 ; j++)
{
if(s[j-1]==t[i-1])
{
dp[i][j] = dp[i-1][j-1]+dp[i][j-1];//状态转移方程
}
else
dp[i][j] = dp[i][j-1];
}
}
return dp[t.length()][s.length()];//返回
}
};```

SQL中的互斥模拟？

PHP+MsSQL=复选框问题。需要帮助！

DBus Glib与C++：不能创建dBug代理，释放它并创建它

Windows 7上的Netbeans 3