What is recursive solution of this spoj problem?

Правка en1, от VIKRAM91, 2018-04-26 20:58:06

I was doing this spoj problem and written tabulation mathod which got accepted, then I written recursive solution but this gave me 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++){
      dp[i][0]=max(dp[i-1][0]+abs(a[i]-a[i-1])+b[i],dp[i-1][1]+abs(a[i]-b[i-1])+b[i]);
      dp[i][1]=max(dp[i-1][0]+abs(b[i]-a[i-1])+a[i],dp[i-1][1]+abs(b[i]-b[i-1])+a[i]);
  }
  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];
    return max(max(ans(a,b,n-1,0)+b[n]+abs(a[n-1]-a[n]),ans(a,b,n-1,1)+b[n]+abs(b[n-1]-a[n])),max(ans(a,b,n- 
    1,0)+a[n]+abs(a[n-1]-b[n]),ans(a,b,n-1,1)+a[n]+abs(b[n-1]-b[n])));
 }

 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];
    }
    cout<<ans(a,b,n-1,2);
    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?

Теги #dp, #recursion, memoization, tabulation

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en9 Английский VIKRAM91 2018-04-27 00:18:39 130
en8 Английский VIKRAM91 2018-04-27 00:12:21 139
en7 Английский VIKRAM91 2018-04-26 23:37:07 64
en6 Английский VIKRAM91 2018-04-26 22:50:21 13
en5 Английский VIKRAM91 2018-04-26 22:20:03 17 Tiny change: ' \n 1,0' -> ' \n 1,0'
en4 Английский VIKRAM91 2018-04-26 21:15:00 12
en3 Английский VIKRAM91 2018-04-26 21:13:11 13
en2 Английский VIKRAM91 2018-04-26 21:12:24 6
en1 Английский VIKRAM91 2018-04-26 20:58:06 1829 Initial revision (published)