unable to do this question pls help
K -ordered lcs unabe to understand
Are you not able to understand the question or you are not able to figure out the solution?
not able to understand it
pls reply and help for the problem
Hi Sourav I will be taking your doubt from this point onwards. First tell me, are you familiar with LCS(longest common subsequence) problem which is based on DP?
yes i am familiar with lcs problem but iām not able to figure out this problem
yeah so this is just a slight modification to it
In lcs you had to find the longest subsequence common to both the strings.
here you have to find the longest subsequence that is possible if you have the option to change at most k elements in the first subsequnece. Basically this means that a subsequence that was not longest earlier can be found out now if we change some elements of the first sequence.
As an example take sequence 1 as 1 2 3 4 5 and seq 2 as 5 3 1 4 2. earlier the LCS would have been 2 (1 2). However if i change the 2 in seq 1 to 5, making it as 1 5 3 4 5, the lcs now would be 3 (5 3 4).