Loading…
Loading…
Fills a table where dp[i][j] is the LCS length of the first i and j characters — each cell built from its diagonal, top, or left neighbour.
Base row & column are 0 (an empty string matches nothing).
1int lcs(String a, String b) {2 int m = a.length(), n = b.length();3 int[][] dp = new int[m+1][n+1];4 for (int i = 1; i <= m; i++)5 for (int j = 1; j <= n; j++)6 if (a.charAt(i-1) == b.charAt(j-1))7 dp[i][j] = dp[i-1][j-1] + 1;8 else9 dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);10 return dp[m][n];11}