[Leetcode Solution] Distinct Subsequnces

GREAT PROBLEM FAILED TO COME UP THE IDEA

Analysis

• Using brutal force search definitely will run exceed time limit
• It's kind of hard to come up with this dynamic programming idea, actually I didn't understand what the problem description mean before I read others blogger
• Let f[i][j] denote the number of distinct subsequence of the substring of S within first i letters in substring of T within first j letters. Then the recursive relation we can find out is 
• f[i][j] = f[i-1][j-1] + f[i-1][j] ( S[i-1]==T[j-1] )
• f[i][j] = f[i-1][j] ( S[i-1]!=T[j-1] )

Note

• When using custom defined type as a parameter in unordered_map, the hash function and comparative function is needed to be defined. However map does not.
• If only know about the recursive relation and terminal condition, but not the order of which variable should loop at first, maybe consider using memorial searching by hash

Code