最长上升子序列(LIS)以及最长公共子序列(LCS)
那么 依据之前的方法,我们还是从设计状态开始
通过此题更加可以看出:DP是一种思想,一种”大事化小,小事化了“的思想。
其关键依然是------我是谁?我从哪里来?我到哪里去?
最长公共子序列:
一个给定序列的子序列是在该序列中删去若干元素后得到的序列。。
而给定两个序列X和Y,当另一序列Z既是X的子序列又是Y的子序列,称Z是序列X和Y的公共子序列。而长度最长的Z便是最后的解。
如:S1 = 1,3,4,5,6,7,7,8
S2 = 3,5,7,4,8,6,7,8,2
求其中最长的公共子序列。
解法:
首先状态(我是谁): 设置一个二维数组,大小为dp[S1.size + 1][S2.size + 1] 。 dp[i][j]便表示 其中以第i个字符结尾的S1子串,和以第j个字符结尾的S2子串的公共子序列。
dp[0][j]与dp[i][0] 均为零 i为第几个 从1开始计数。
空白格子填入的便是我们记录的LCS的长度。
规则依据递归公式: 如果(i,j)对应的元素相等,那么格子内的值便为(dp[i - 1][j - 1] + 1),如果不等便为max(dp[i - 1][j], dp[i][j - 1])
至此,填完该表,并且得到答案。
首先 dp[1][1] 长度为0(1和3没有) dp[2][1] 长度为1
得到DP后,我们可以通过倒推来得到相应的子序列。
我们知道S1和S2的LCS并不是只有一个,
在倒推时,如果s1[i] == s2[j] 就跳转到c[i - 1][j - 1],如果s1[i] != s1[j], 就向前找或向上找(只能一个方向)