C++ 最长公共子序列 Sub Sequence
最长公共子序列是一个经典的基础算法问题 在两个序列中 如果序列1中的元素a也存在于序列2，则认为a是1，2的公共元素。 当序列3中的每一个元素都能够满足在不改变次序的情况下依次属于1，2，那么则认为3是1，2的公共子序列。多个公共子序列中，元素最多的即为最长公共子序列。
在学堂在线的算法课程中，有比较详细的课程讲述这个算法的构思。但是没有给出具体的实现，这里来自己实现一下。
首先使用表格模拟排列组合的所有情况: 以{a,b,c,d,e},{a,b,q,c,b}为例:
| A\B | a | b | q | c | b |
|---|---|---|---|---|---|
| a | 1 | 1 | 1 | 1 | 1 |
| b | 1 | 2 | 2 | 2 | 2 |
| c | 1 | 2 | 2 | 3 | 3 |
| d | 1 | 2 | 2 | 3 | 3 |
| e | 1 | 2 | 2 | 3 | 3 |
实际上看到这样的填充，直觉上就应该反应出来，使用二维数组来解决。
其中当 A[i]!=B[j]时，取左方或者上方更大的，而A[i]==B[j]的时候，取T[i-1][j-1] + 1。这里i=0或j=0的时候就不方便了，所以给矩阵默认增加一行 0 行。即
| A\B | 0 | a | b | q | c | b |
|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| a | 0 | 1 | 1 | 1 | 1 | 1 |
| b | 0 | 1 | 2 | 2 | 2 | 2 |
| c | 0 | 1 | 2 | 2 | 3 | 3 |
| d | 0 | 1 | 2 | 2 | 3 | 3 |
| e | 0 | 1 | 2 | 2 | 3 | 3 |
最近回复