115不同的子序列

本题有两种思路：

• 在s中找到t的开头字母，假设s[1]==t[0],那么dp(s,1,t,0)就等于dp(s,2,t,1);
• 假设在s中找到s[i]==t[j],那么将会有两种情况：1.就让i位置和j匹配：dp(s,i+1,t,j+1)2.不让i位置和j匹配：dp(s,i+1,t,j);

如果i和j的位置都不匹配当然直接算dp(s,i+1,t,j);无论什么情况都会i+1,因此不需要for循环。

dp(string s,int i ,string t,int j){
  if(j==t.size())return 1;//j的指针已经走过最后一位了
  if((s.size()-i)<(t.size()-j))return 0;
  int res=0;
  if(mem[i][j]!=-1)return mrm[i][j];
  for(int k=i;k<s.size();k++){
    if(s[k]==t[j]){
      res+=dp(s,k+1.t.j+1);
    }
  }
  mem[i][j]=res;
  return mem[i][j];
}

dp(string s,int i,string t,int j){
  if(j==t.size())return 1;
  if((s.size()-i)<(t.size()-j)){
    return 0;
  }
  if(mem[i][j]!=-1)return mem[i][j];
  if(s[i]==t[j]){
    res+=dp(s,i+1,t,j+1)+dp(s,i+1,t,j);
  }else{
    res+=dp(s,i+1,t,j);
  }
  mem[i][j]=res;
  return mem[i][j];
}