UVA 10405 Longest Common Subsequence：简单DP

UVA 10405 Longest Common Subsequence：简单DP2015-02-17省赛还有不到50天了，自己DP这块实在是弱，准备就拿着些天狂刷DP了。

http://uva.onlinejudge.org/index.php？option=com_onlinejudge&Itemid=8&page=show_problem&problem=1346

大意：求两个字符串的最长公共子序列。

思路：水题，不过需要注意的就是字符串里可能会出现空格，需要用gets,真是坑。

#include <stdio.h>#include <string.h>#define max（a, b） a>b？a:bchar s1[1010], s2[1010];int dp[1010][1010];int main（）{while（gets（s1））{gets（s2）;memset（dp, 0, sizeof（dp））;int len1 = strlen（s1）;int len2 = strlen（s2）;for（int i = 1; i <= len1; ++i）{for（int j = 1; j <= len2; ++j）{if（s1[i-1] == s2[j-1]）{dp[i][j] = dp[i-1][j-1]+1;}else{dp[i][j] = max（dp[i-1][j], dp[i][j-1]）;}}}printf（"%d
", dp[len1][len2]）;}return 0;}Accepted

From：cnblogs GLSilence