Why a 3-D DP is required?

#1

I am not able to understand why we need to keep a separate state for k .
For arrays A and B , indices i and j.
I applied the logic that :

  1. If elements of A and B are same , dp[i][j] = 1 + dp[i-1][j-1] and proceed to i+1 and j+1 as normal .
  2. If both are different , find if we really need to edit the A[i] using k , i.e if after editing it we are getting 1+dp[i-1][j-1] as greater than dp[i-1][j] and dp[i][j-1].

I am able to pass several test cases but not all .
Please see through code

image
image719×582 83 KB 

int lenModifiedLCS(vector<int>& A,vector<int>&B,int k)
{
    int N = A.size();
    int M = B.size();
    vector<vector<int>> dp(N+1,vector<int>(M+1,0));
    
    for(int i=1;i<=N;i++)
    {
        for(int j=1;j<=M;j++)
        {
            // i-1 and j-1 are indices of arrays
            // i and j are indices of dp table
            if(A[i-1] == B[j-1])
            {
                dp[i][j] = 1 + dp[i-1][j-1];
            }
            else
            {
                int possibleChange = 1 + dp[i-1][j-1];
    if(
    k>0 && 
        (possibleChange == max(max(possibleChange,dp[i-1][j]) , dp[i][j-1])) &&
        (possibleChange != dp[i-1][j]) && (possibleChange!=dp[i][j-1])
    )
                {
                    A[i-1] = B[j-1];
                    dp[i][j] = possibleChange;
                    k--;
                }
                
                
                else
                {
                    dp[i][j] = max( dp[i-1][j] , dp[i][j-1]  );
                }
            }
            
        }
    }
    
    // for(int i=0;i<N+1;i++)
    // {
    //     for(int j = 0;j<M+1;j++)
    //     {
    //         cout<<setw(3)<<dp[i][j]<<" ";
    //     }
    //     cout<<"\n";
    // }
    
    return dp[N][M];
    
}
#2

Hello @nipunbinjola,

The third dimension k is used to store the best/optimal length of matched string with k changes.

This is useful for the case:
When we have done 1 change: res=1+f(i+1,j+1,k-1)
So, if we have already calculated the optimal value fro k-1, then we can just directly look up it’s value from the matrix.
This refers to Optimal Substructure property of DP.

Now, coming back to your code:
Yes, we can do it without the third dimension also.
Your code is producing wrong output for the testcases like:
5 6 3
1 2 3 4 5
5 3 1 3 2 5
Expected Output:
5
Your Output:
4

You can execute the following code, to understand your mistake.

Hope, this would help.
Give a like, if you are satisfied.

#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.