最长公共子序列（LCS）是经典的DP问题，求序列a[1...n]， b[1..m]的LCS。
状态是DP[i][j]，表示a[1..i]，b[1..j]的LCS。
DP转移方程是
DP[i][j]=
DP[i-1][j-1]+1, a[i] == b[j]
max{ DP[i][j-1], DP[i-1][j] }, a[i] != b[i]
-------------------------------------------------------------------------------------------
时间复杂度O(N^2)，空间复杂度0（N^2)。
使用滚动数组，可将空间复杂度降到 0(N)。
观察DP转移方程可看出，即使用滚动数组，也需要两个即DP[2][N]，一个DP[N]行不通。
因为若只用一维数组DP[N]来保存状态，第一个式子要求从右向左更新，第二个式子要求从左向右更新。
------------------------------------------------------------------------------------
以上关于用滚动数组降低空间复杂度的论述有误
------------------------------------------------------------------
实际上只用一维数组DP[N]也可以，只消将第一个转移方程略作改动。严格地说，上面的论述并没有错，若严格按照
DP[i][j]=
DP[i-1][j-1]+1, a[i] == b[j]
max{ DP[i][j-1], DP[i-1][j] }, a[i] != b[i]
来转移，一个DP[N]确实不够，但我们深入分析下一开始的论据--"第一个式子要求从右向左更新",
如果第一式也从左向右更新，那么在需要DP[i-1][j-1]时，它已被DP[i][j-1]覆盖。
---------------------------------------------------------------------------------------------------------------------------------------
我们略微变通一下，将第一个转移方程改为
DP[i][j] = max{ DP[i-1][k] : k < j } +1
这样只要在从左到右更新时维护一个max{ DP[i-1][k] : k < j }。
----------------------------------------------------------------------------------------------------------------------------
Longest Common Subsequence (LCS)
原文：http://www.cnblogs.com/Patt/p/4735190.html