Wrong answer top down dp

#1

i am not getting the correct answer from bottom up dp
please help

#2

@Aparna
Please have a look at the code.

for (int k = 0; k <= K; k++) {
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			if (a[i - 1] == b[j - 1]) {
				dp[i][j][k] = dp[i - 1][j - 1][k] + 1;
			}
			else {
				if (k > 0)
					dp[i][j][k] = dp[i - 1][j - 1][k - 1] + 1;
				dp[i][j][k] = max({dp[i][j][k], dp[i - 1][j][k], dp[i][j - 1][k]});
			}
		}
	}
}
cout << dp[n][m][K];
#3

what is lt? and i think you hqve shared wrong code file

#4

@Aparna
Ah, The link got messed up.
Here is the code.

#5

still wrong answer, please check https://ide.codingblocks.com/s/296848

#6 
int n,m,K;
cin>>n>>m>>K;
int arr1[n];
int arr2[m];
for(int i=0;i<n;i++){
	cin>>arr1[i];
}
for(int i=0;i<m;i++){
	cin>>arr2[i];
}
int dp[n+1][m+1][K+1];
memset(dp,0,sizeof(dp));
for(int k=0;k<=K;k++){
    for(int i=1;i<=n;i++){
	    for(int j=1;j<=m;j++){
			if(arr1[i-1]==arr2[j-1]){
				dp[i][j][k] = dp[i-1][j-1][k] + 1;
			}
			else{
				if (k > 0)
					{ dp[i][j][k] = dp[i - 1][j - 1][k - 1] + 1; }
				dp[i][j][k] = max({dp[i][j][k], dp[i - 1][j][k], dp[i][j - 1][k]});
			}
		}
	}
}
cout<<dp[n][m][K]<<endl;
return 0;

}

you were doing cin>>arr2[i] both the times.
Please try to debug the code yourself before asking, that will help you improve drastically.

#7

oh! i was looking at the main code, these small bugs sometimes are much harder to find :stuck_out_tongue: thanks though :slight_smile: