K - Ordered LCS

#1

Hey CB, how can i solve this problem using bottom up approach?

#2

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
Time complexity = O(n * m * k)

Reference Code