Longest Common subsequence

Given 2 strings, find the longest common subsequence using dynamic programming.

public class LongCommonSubSequence {

	//Returns length of LCS for x[0..m-1], y[0..n-1] 
	public static int lcs(String x, String y) {
		int M = x.length();
		int N = y.length();

		// opt[i][j] = length of LCS of x[i..M] and y[j..N]
		int[][] opt = new int[M + 1][N + 1];

		// compute length of LCS and all subproblems via dynamic programming
		for (int i = M - 1; i >= 0; i--) {
			for (int j = N - 1; j >= 0; j--) {
				if (x.charAt(i) == y.charAt(j))
					opt[i][j] = opt[i + 1][j + 1] + 1;
				else
					opt[i][j] = Math.max(opt[i + 1][j], opt[i][j + 1]);
			}
		}

		// recover LCS itself and print it to standard output
		int i = 0, j = 0;
		while (i < M && j < N) {
			if (x.charAt(i) == y.charAt(j)) {
				System.out.print(x.charAt(i));
				i++;
				j++;
			} else if (opt[i + 1][j] >= opt[i][j + 1])
				i++;
			else
				j++;
		}
		System.out.println();
		return opt[0][0];
	}

	/* Driver program to test above function */
	public static void main(String args[]) {
		String str1 = "AGGTAB";
		String str2 = "GXTXAYB";
		System.out.println("Length of LCS is" + lcs(str1, str2));
	}
}