动态规划之两个数组的dp问题（最长公共子序列）

leetcode1143题为例

 题目要求：

1.子序列

2.公共子序列的最长长度

算法原理：

经验：对于字符串的问题，我们一般是以一段区间为研究对象，因为绝大多是以某个位置为结尾解决不了问题

dp[i][j]:表示以s1的0到i区间，s2的0到j区间的所有子序列中（所有是包含以i结尾和不包含i结尾的所有子序列），最长公共子序列的长度

状态转移方程：根据最后一个位置的状况，分情况讨论

1.如果s[i]==s[j]，那这个最长公共子序列肯定包含这两个相同的元素 ，只要在后面+1即可

2.如果不相等，那就需要在dp[i-1][j]和dp[i][j-1]和dp[i-1][j-1]中去找，然后取max

但第一种和第二种包含第三种，有和没有都一样，优化中我们可以去掉第三种

第一点：首先要明白空串是有研究意义的，如果公共子序列是空串就返回0

那我们可以多加一行多加一列，最上面一行表示dp[0][j]：第一个字符串是空串

第一列就表示第二个字符串是空串

那这些多加的都要初始化为0（当空串的时候公共子序列的最长长度就是0）

我们在初始化时多加一行多加一列就不会越界访问 

第二点：注意下标映射关系，但这里字符串我们可以简单处理一下

就是在每个字符串前面加一个“-”或者什么字符都可以，填表时就是从s[1]开始比较，所以填表时就是对应的

观察我们的状态转移方程，填表时需要用到哪些位置，当你填一个位置时，需要用到上面，左上，左下的位置，所以我们需要先算这些位置的值，才能算出你要填那个位置的值

所以填表顺序需要从上往下，从左往右

返回值：看定义的状态，那就是返回dp[n][m]; 

代码编写：