tips : 本文内容是参考了很多著名博客和自己的思考得出的，如有不当欢迎拍砖。
先简单说一下动态规划
通俗地说：动态规划就是将一个可以划分为子问题的问题进行递归求解，不过动态规划将大量的中间结果保存起来，
为代价换取时间的算法。
对于最长公共子序列的题目不用多说，现在来分析一下LCS的动态规划解决思路：
一、首先先观察问题是否符合动态规划最明显的两个特征：最优子结构和重叠子问题
方便起见，以x = {a,d,f,s,d}序列和y = {a,s,d,f}序列为例进行说明，z序列为x序列和y序列的最长公共子序列。
1. 最优子结构
首先观察x序列和y序列的第一项可知x1=y1，因此a肯定是z中的第一项。接下来，由于x2!=y2，因此对于z序列中
z2-zn存在两种情况：要么z2-zn存在于[{d,f,s,d}，{d,f}]中或者存在于[{f,s,d},{s,d,f}]中。但是不管最终是哪
种情况，都避免不了要计算[{f,s,d},{d,f}]这种情况。由此可得该问题满足最优子结构的特点。
2.重叠子问题
前面说到，求x序列和y序列的最长公共子序列有可能会求x-1和y的子序列或者求x和y-1的子序列，，而对这两种情
况进行递归求解的时候，都会涉及到求x-1和y-1的情况，也就是说存在重叠子问题的特点。
二、建立状态转移方程
用mix[a][b]来记录xa和yb的最长子序列，当x[a]=y[b]时：mix[a][b] = mix[a-1][b-1] + 1；当x[a]!=y[b]
时：mix[a][b]=MAX{mix[a-1][b]，mix[a][b-1]}。即：
mix[a][b] = mix[a-1][b-1] + 1x[a] = y[b]
mix[a][b] =MAX{mix[a-1][b]，mix[a][b-1]}x[a] !=y[b]
由以上分析不难得出代码如下：
import java.util.Scanner;public class Main {static String[] str1;static String[] str2;// 使用矩阵记录数据static int[][] mix;public static void main(String[] args) {Scanner sc = new Scanner(System.in);str1 = sc.nextLine().trim().split(" ");str2 = sc.nextLine().trim().split(" ");sc.close();// 初始化矩阵mix = new int[str2.length + 1][str1.length + 1];// DP填充矩阵lcs();// 打印矩阵printMix();System.out.println("最长公共子序列的长度:" + mix[str2.length][str1.length]);}/** * DP填充矩阵 */private static void lcs() {for (int a = 1; a < str2.length + 1; a++) {for (int b = 1; b < str1.length + 1; b++) {if (str2[a – 1].equals(str1[b – 1])) {mix[a][b] = mix[a – 1][b – 1] + 1;} else {mix[a][b] = Math.max(mix[a – 1][b], mix[a][b – 1]);}}}}/** * 打印矩阵数据 */private static void printMix() {System.out.println("打印矩阵数据：");System.out.print(" ");for (String s : str1) {System.out.print(s + " ");}System.out.println();for (int a = 1; a < str2.length + 1; a++) {System.out.print(str2[a – 1] + " ");for (int b = 1; b < str1.length + 1; b++) {System.out.print(mix[a][b] + " ");}System.out.println();}}}
对于测试数据：x = {a,d,f,s,d}序列和y = {a,s,d,f}的执行结果如下：
送给中意的TA，背面写上：某年某月某日，
