Why is my recursive solution of this(link given) spoj problem giving me WA?

Revision en9, by VIKRAM91, 2018-04-27 00:18:39

I was doing this Spoj problem and written tabulation method which got accepted, then I have written recursive solution but this gave me the wrong solution(WA), Where is my recursive solution is wrong:-

Below is my tabulation solution which got AC:-

#include<bits/stdc++.h>
using namespace std;
int main(){
  int n;
  cin>>n;
  int a[n]={0};
  int b[n]={0};
  for(int i=0;i<n;i++){
      cin>>a[i]>>b[i];
  }
  int dp[n][2]={{0}};
  dp[0][0]=b[0];
  dp[0][1]=a[0];
  for(int i=1;i<n;i++){
      int x=dp[i-1][0]+abs(a[i]-a[i-1])+b[i];
      int y=dp[i-1][1]+abs(a[i]-b[i-1])+b[i];
      int s=dp[i-1][0]+abs(b[i]-a[i-1])+a[i];
      int t=dp[i-1][1]+abs(b[i]-b[i-1])+a[i];
      dp[i][0]=max(x,y);
      dp[i][1]=max(s,t);
  }
  cout<<max(dp[n-1][0],dp[n-1][1]);
  return 0;
 }

And below is my recursive solution which is giving me WA:-

#include<bits/stdc++.h>
 using namespace std;

 int ans(int a[],int b[],int n,int j){
    if(n==0&&j==0)
       return b[0];
    if(n==0&&j==1)
       return a[0];
    int x=ans(a,b,n-1,0)+b[n]+abs(a[n-1]-a[n]);
    int y=ans(a,b,n-1,1)+b[n]+abs(b[n-1]-a[n]);
    int s=ans(a,b,n-1,0)+a[n]+abs(a[n-1]-b[n]);
    int t=ans(a,b,n-1,1)+a[n]+abs(b[n-1]-b[n]);
    return max(max(x,y),max(s,t));
}

 int main(){
    int n;
    cin>>n;
    int a[n]={0};
    int b[n]={0};
    for(int i=0;i<n;i++){
       cin>>a[i]>>b[i];
    }
    if(a[0]>b[0])
        cout<<ans(a,b,n-1,1);
    else cout<<ans(a,b,n-1,0)
    return 0;
  }

I want to ask:-

1). What is wrong with my recursive solution.

2). Can we do all dp problem with tabulation and memoization i.e if we can do with memoization than can we do with tabulation and vice versa for every dp problem?

Tags #dp, #recursion, memoization, tabulation

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en9 English VIKRAM91 2018-04-27 00:18:39 130
en8 English VIKRAM91 2018-04-27 00:12:21 139
en7 English VIKRAM91 2018-04-26 23:37:07 64
en6 English VIKRAM91 2018-04-26 22:50:21 13
en5 English VIKRAM91 2018-04-26 22:20:03 17 Tiny change: ' \n 1,0' -> ' \n 1,0'
en4 English VIKRAM91 2018-04-26 21:15:00 12
en3 English VIKRAM91 2018-04-26 21:13:11 13
en2 English VIKRAM91 2018-04-26 21:12:24 6
en1 English VIKRAM91 2018-04-26 20:58:06 1829 Initial revision (published)