Dynamic Programming 2

Harder DP Questions: most 2 sequenced DP

• state: f[i][j]代表了第一个sequence的前i个数字/字符 配上第二个sequence的前j个...
• function: f[i][j] = 研究第i个和第j个的匹配关系
• intialize: f[i][0] 和 f[0][i]
• answer: f[s1.length()][s2.length()]

相似题目：

    Longest Common Substring
    Longtest Common Subsequence

    Distinct Subsequences
    Edit Distance
    Interleaving String

重点

确立 当A[i-1] == B[j-1]时的前后关系 当A[i-1] != B[j-1]时的前后关系