1int lcs(char *s1, char *s2, int m, int n) {
2 int dp[m+1][n+1];
3 for (int i = 0; i <= m; i++)
4 for (int j = 0; j <= n; j++) dp[i][j] = 0;
5 for (int i = 1; i <= m; i++) {
6 for (int j = 1; j <= n; j++) {
7 if (s1[i-1] == s2[j-1])
8 dp[i][j] = dp[i-1][j-1] + 1;
9 else
10 dp[i][j] = dp[i-1][j] > dp[i][j-1] ? dp[i-1][j] : dp[i][j-1];
11 }
12 }
13 return dp[m][n];
14}
