How to approach

#1

I am not able to think about the approach. Kindly give me some suggestions.

#2

As you know these problems are variations of classical dynamic programming problems. so first you need to mathematically formulate the solution.
once you will formulate the recursive step mathematically and find the optimal substructure , your task is done.
here one extra parameter is k.
So,
f(a1,a2,i,j,k) = { 1+f(a1,a2,i+1,j+1,k) ; if a1[i]==a2[j]
max{1+f(a1,a2,i+1,j+1,k-1) , f(a1,a2,i,j+1,k), f(a1,a2,i+1,j,k) }; if a1[i]!=a2[j] and k>0

a1, a2 are two arrays and i,j are current indices starting with 0.

now you can try to write this mathematical function using java code. you just need to think that how to memorize the already computed value(optimal substructure)

Thanks

#3

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.