http://poj.org/problem?id=1080
http://acm.hdu.edu.cn/showproblem.php?pid=1080
1 | #include <iostream> |
后来发现是自己想得太多了,这个题的“状态”不一定非要理解成原先那样,
其实完全可以也像最大公共子列那样的,
dp[x][y]表示str1的前x个字符和str2的前y个字符之间的匹配结果的最优解
这样也便于理解,便于思考
这样的话dp[x][y]就是最终答案,不过要注意边界的预处理
代码如下
1 | #include <iostream> |