(a) Why is the Principle of Optimality important for dynamic programming method? (b)For the Longest Common Subsequence (LCS) problem with input X=x1x2xm and Y=y1y2yn, we solved the problem using the dynamic programming method where we defined cij to be the length of a LCS between x1x2xi and y1y2yj. What is the complete recurrence for cij, including the initial condition? For the following X=ABCAD and Y=DADC : fill the following table with the values of cij 's