最长子串

数学归纳法：
以 dp(str1,str2) 代表对 str1 和 str2 求最长子序列

# str[i] 代表 str[0:i] 子串
# =>1
    str1 = B # 紫色
    str2[] = A, AB,...,ABAZDC
    for str2 in str2[]:
        dp(str1, str2)
# => i
    # 末尾字符串相同:
      str1 = '...A'
      str2 = '....A'
      # 此时所求最长公共子序列为
      dp(str1[i-1], str2[i-1]) + 1
  末尾字符串不同:
      str1 = '...A'
      str2 = '....B'
      max(dp(str[i-1],str[i]), dp(str[i],str[i-1]))

程序示例：

string1 = "BACBAD"
string2 = "ABAZDC"
dp = [0] * (len(string2) + 1)
for i in range(1, len(string1) + 1):
    str1 = string1[:i]
    for j in range(1, len(string2) + 1):
        str2 = string2[:j]
        if str1[-1] == str2[-1]:
            dp[j] = dp[j - 1] + 1
            continue
        if str1[-1] != str2[-1]:
            dp[j] = max(dp[j - 1], dp[j])
            continue
    print(*dp, sep=" ")