The given code is for the question from HackerChef Kth Order LCS. The code is working it is giving correct output. I wanted to check how many times the DP array is returning the value in order to see how much steps i have saved. so for that i created a global variable counter which counts the steps.
input:
5 5 1
1 2 3 4 5
5 3 1 4 2
output:
0 3
my expected output:
14(assumed) 3
code:
#include
#include
#define ll long long
using namespace std;
int count; //The counter variable
ll a[2005],b[2005],n,n1;
ll dp[2005][2005][8];
ll KLCS_DP(ll i,ll j,ll k)
{
if(i >= n || j >= n1)
return 0;
int x1=0,x2=0,x3=0,x4=0;
if(dp[i][j][k] != -1)
{
count++; //counter increment
return dp[i][j][k];
}
if(a[i] == b[j])
{
x1 = 1 + KLCS_DP(i+1,j+1,k);
}
else
{
if(k > 0)
{
x2 = 1 + KLCS_DP(i+1,j+1,k-1);
}
x3 = KLCS_DP(i+1,j,k);
x4 = KLCS_DP(i,j+1,k);
}
int result = max(max(x1,x2),max(x3,x4));
dp[i][j][k] = result;
return result;
}
int main()
{
memset(dp,-1,sizeof(dp));
count = 0; //counter variable initialization
ll i,k;
cin>>n>>n1>>k;
for(i=0;i<n;i++)
cin>>a[i];
for(i=0;i<n1;i++)
cin>>b[i];
cout<<count<<" "; // counter variable print
cout<<KLCS_DP(0,0,k);
return 0;
}