Today I solved the problem . Link : http://lightoj.com/volume_showproblem.php?problem=1157
I have a question . If the problem is modified and say to find the number of distinct common sub-sequences of n ( 0<=n<=1000 ) length than is it possible to come up a solution ?
let A = "abba" ans B = "abba" , here LCS between A and B is 4 . So number of distinct LCS between A and B is 1 . But if said find the number of distinct common sub-sequences of 3 length than answer will be 3 ( "abb" , "aba" , "bba" ) .
Auto comment: topic has been updated by rajon_aust (previous revision, new revision, compare).
26 * (N ^ 2) * needLength solution.
dp[i][j][len] — count of subsequences with length len and last symbol we took in seq A was sym at pos i, last sym we took in seq B was sym at pos j.
Update other state: lets fix symbol C. find leftmost position pos such that pos > i && a[pos] == C, find leftmost position pos2 such that pos2 > j && b[pos2] == C, update state (pos, pos2, len + 1);
Thanks !
Auto comment: topic has been updated by rajon_aust (previous revision, new revision, compare).