蓝桥杯 ADV-202 算法提高 最长公共子序列(动态规划)

问题描述
  给定两个字符串,寻找这两个字串之间的最长公共子序列。
输入格式
  输入两行,分别包含一个字符串,仅含有小写字母。
输出格式
  最长公共子序列的长度。
样例输入
abcdgh
aedfhb
样例输出
3
样例说明
  最长公共子序列为a,d,h。
数据规模和约定
  字串长度1~1000。
分析:求最长公共子序列,用动态规划~只需建立一个长宽为两个字符串长度+1的二维数组~dp[i][j]表示String a的前i个字符构成的字符串和String b的前j个字符构成的字符串这两者得到的最长公共子序列的长度为dp[i][j]~~~所以第0行和第0列所有的数都为0~
根据递推公式:

Snip20160525_13

按一行一行的顺序填入数~

最后一个格子的长度就是两个字符串的最长公共子序列的长度~~