How do I solve this problem?

#1

What will be the intuition here?

#2

@ap8730390
As mentioned in the problem statement, given problem is quite similar to the standard LCS problem. We can have following dp state DP(n,m,k) = denotes LCS for first n number of first array, first m numbers of second array when we are allowed to change at max k numbers in first array.

Recursion look like this ->
DP(n,m,k) = max(DP(n-1,m,k), DP(n, m-1, k), DP(n-1, m-1, k-1)+1), if arr[n]!=arr[m]
DP(n,m,k) = max(DP(n-1,m,k), DP(n, m-1, k), DP(n-1, m-1, k)+1), if arr[n]==arr[m]
The total number of distinct states, hence are = n * m * k

#3

IF arr[n]== arr[m], DP(n,m,k) = 1 + DP(n-1,m-1,k)+1 kyu nhi hoga?

#4

@ap8730390
try krke dekho

#5

Mera approach Kaam kar toh gaya… Recursive solution ajeeb tarah se likha hua hai

#6

@ap8730390 ajeeb matlb ?

#7

DP(n,m,k) = max(DP(n-1,m,k), DP(n, m-1, k), DP(n-1, m-1, k)+1), if arr[n]==arr[m]

aapne yeh likha tha na in case characters match. When the characters match toh sirf isse DP(n-1, m-1, k)+1 hi kaam ho jaayega. 3 cheezon ka max kyu lena?

#8

@ap8730390 tumhara code bhi sahi h

#9

Ek aur cheez . Yeh Bottom Up se kaise hoga ? 3d dp lekar kuch karna padega?

#10

@ap8730390
3d dp ka dp table 2D ki taraf fill hota h.
3D dp bahut km aata h Contest me .

1 Like