动态规划法实现最长公共子序列

动态规划法实现最长公共子序列的过程如下：
1. 定义一个二维数组arr[m+1][n+1]，其中m和n分别为两个字符串的长度。
2. 初始化arr数组的第一行和第一列为0。
3. 从第二行和第二列开始，遍历两个字符串的每个字符，如果两个字符相等，则arr[i][j] = arr[i-1][j-1] + 1；否则，arr[i][j] = max(arr[i-1][j], arr[i][j-1])。
4. 遍历完两个字符串后，arr[m][n]即为最长公共子序列的长度。
5. 通过回溯法，可以获取公共子序列的所有序列并打印。

举个例子，假设有两个字符串s1="ABCBDAB"和s2="BDCABA"，则动态规划表如下：

| | | B | D | C | A | B | A |
|---|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| A | 0 | 0 | 0 | 0 | 1 | 1 | 1 |
| B | 0 | 1 | 1 | 1 | 1 | 2 | 2 |
| C | 0 | 1 | 1 | 2 | 2 | 2 | 2 |
| B | 0 | 1 | 1 | 2 | 2 | 3 | 3 |
| D | 0 | 1 | 2 | 2 | 2 | 3 | 3 |
| A | 0 | 1 | 2 | 2 | 3 | 3 | 4 |
| B | 0 | 1 | 2 | 2 | 3 | 4 | 4 |

其中，arr = 4，即最长公共子序列的长度为4，而公共子序列有多个，如"BDAB"、"BCAB"、"BCBA"等。