是最长公共子序列（Longest Common Subsequence，LCS）的一种变形。典型的动态规划题目
经典的最长公共子序列描述：
给定两个序列
X = { x1 , x2 , ... , xm }
Y = { y1 , y2 , ... , yn }
求X和Y的一个最长公共子序列

举例
X = { a , b , c , b , d , a , b }
Y = { b , d , c , a , b , a }
最长公共子序列为
LSC = { b , c , b , a }
最长公共子序列问题具有最优子结构性质

设
X = { x1 , ... , xm }
Y = { y1 , ... , yn }
及它们的最长子序列
Z = { z1 , ... , zk }

则
1、若 xm = yn ， 则 zk = xm = yn，且Z[k-1] 是 X[m-1] 和 Y[n-1] 的最长公共子序列
2、若 xm != yn ，且 zk != xm , 则 Z 是 X[m-1] 和 Y 的最长公共子序列
3、若 xm != yn , 且 zk != yn , 则 Z 是 Y[n-1] 和 X 的最长公共子序列

由性质导出子问题的递归结构，设c[i][j]表示x的前i个组成的子序列和y的前j个组成的子序列最大子序列长度
当 i = 0 , j = 0 时 , c[i][j] = 0
当 i , j > 0 ; xi = yi 时 , c[i][j] = c[i-1][j-1] + 1
当 i , j > 0 ; xi != yi 时 , c[i][j] = max { c[i][j-1] , c[i-1][j] }
最后求得的c[lenX][lenY]就是X和Y的最长公共子序列长度。

本题要求的是最大的bonus，因此根据稍作修改：
当 i = 0 , j = 0 时 , c[i][j] = 0
当 i , j > 0 ; xi = yi 时 , c[i][j] = c[i-1][j-1] + bonus[c[i]]//事先存储在数组中
当 i , j > 0 ; xi != yi 时 , c[i][j] = max { c[i][j-1] , c[i-1][j] }

但题目的字符串长度是10000，因此如果定义c[10000][10000]就会超内存，因此需要减少内存。
从上面的递归结构可以发现，c[i][j]只与c[i-1][j-1],c[i][j-1]或c[i-1][j]，也就是第i行只与本行或上一行有关。因此前面用过的内存都可以释放。
只需要定义2行大小既可，即c[2][10000];
如果i行是奇数行：
if(x[i-1]==y[j-1])
 c[1][j] = c[0][j-1]+bonus[x[i-1]];
else
 c[1][j] = max(c[1][j-1],c[0][j]);
否则：
if(x[i-1]==y[j-1])
 c[0][j] = c[1][j-1]+bonus[x[i-1]];
else
 c[0][j] = max(c[0][j-1],c[1][j]);
最后的答案是c[lenX%2][lenY]，跟总共是奇数行还是偶数行有关。