title: Distinct Subsequences DP explanation
body: <p>From <a href="http://oj.leetcode.com/problems/distinct-subsequences/" rel="noreferrer">LeetCode</a></p>
  
  <blockquote>
    <p>Given a string S and a string T, count the number of distinct
    subsequences of T in S.</p>
    
    <p>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).</p>
    
    <p>Here is an example: S = "rabbbit", T = "rabbit"</p>
    
    <p>Return 3.</p>
  </blockquote>
  
  <p>I see a very good DP solution, however, I have hard time to understand it, anybody can explain how this dp works?</p>
  
  <pre><code>int numDistinct(string S, string T) {
  
      vector&lt;int&gt; f(T.size()+1);
  
      //set the last size to 1.
      f[T.size()]=1;
  
      for(int i=S.size()-1; i&gt;=0; --i){
          for(int j=0; j&lt;T.size(); ++j){
              f[j]+=(S[i]==T[j])*f[j+1];
              printf("%d\t", f[j] );
          }
          cout&lt;&lt;"\n";
      }
      return f[0];
  }
  </code></pre>