文章作者：ktyanny 文章来源： 转载请注明，谢谢合作。
ktyanny本打算复习考试周研究一下动态规划，今天早上起得很晚，爬起来就想起这件事了，找到一个最水的最长公共子序列的题目，其实算是裸题了。
题目的意思就是给出两个串x和y，让你输出出他们的最长公共子序列（LCS）的长度。于是在纸上模拟了半晌，终于搞懂了记忆化（memoization）是怎么个原理了。下面讲讲LCS的过程吧：
LCS - LENGTH(X, Y, m, n) for i ← 1 to m do c[i, 0 ] ← 0 for j ← 0 to n do c[ 0 , j] ← 0 for i ← 1 to m do for j ← 1 to n do if xi = yj then c[i, j] ← c[i - 1 , j - 1 ] + 1 else if c[i - 1 , j] ≥ c[i, j - 1 ] then c[i, j] ← c[i - 1 , j] else c[i, j] ← c[i, j - 1 ] return c and b
好！根据上面的伪代码，自己跟踪一下c[i][j]数组的变化情况问题就变得很清晰了。
下面是1159的ac代码
46MS C++
#include < iostream > #include < string .h > using namespace std; const int MAX = 1000 ; int c[MAX + 5 ][MAX + 5 ]; int lcs( char * x, char * y, int c[][MAX + 5 ]){ int i, j, m = strlen(x), n = strlen(y); for (i = 0 ; i < m; i ++ ) c[i][ 0 ] = 0 ; for (i = 0 ; i < n; i ++ ) c[ 0 ][i] = 0 ; for (i = 0 ; i < m; i ++ ) { for (j = 0 ; j < n; j ++ ) { if (x[i] == y[j]) c[i + 1 ][j + 1 ] = c[i][j] + 1 ; else if (c[i][j + 1 ] >= c[i + 1 ][j]) c[i + 1 ][j + 1 ] = c[i][j + 1 ]; else c[i + 1 ][j + 1 ] = c[i + 1 ][j]; } } return c[m][n];} int main(){ char x[MAX]; char y[MAX]; while (cin >> x >> y) cout << lcs(x, y, c) << endl; return 0 ;}
下面记下流水账。
上个星期伙食吃超支了，吃了两次麦当劳，打了一次火锅，光了四次超市，昨天还去地下商场吃大家乐。再这样逍遥下去的话我就木有米吃饭了。昨晚睡觉也很玄，可能吃太好了。是这个学期第二次梦到我有一部笔记本了，不过结局好惨，居然被我玩到着火了，囧……第一次梦到自己有笔记本是妈妈说同意我用自己的奖学金买笔记本。等奖学金拿到手的时候， 我倒是想买个电磁炉，因为预测到寒假的饭菜肯定很难啃，想自己学着炒菜啊，好吃又便宜的。嘎嘎……