Memoization and RE - Codeforces

#	User	Rating
1	tourist	3985
2	jiangly	3814
3	jqdai0815	3682
4	Benq	3529
5	orzdevinwang	3526
6	ksun48	3517
7	Radewoosh	3410
8	hos.lyric	3399
9	ecnerwala	3392
9	Um_nik	3392

#	User	Contrib.
1	cry	169
2	maomao90	162
2	Um_nik	162
4	atcoder_official	161
5	djm03178	158
6	-is-this-fft-	157
7	adamant	155
8	awoo	154
8	Dominater069	154
10	luogu_official	150

I was solving this : https://leetcode.com/problems/minimum-jumps-to-reach-home/ and wrote essentially 2 same solutions, just the way of calculating transitions is a bit different. I get AC in one and RE in the second. I am not getting the reason for such a difference in results. So please help me understand.

One which gives RE

class Solution {
public:
   
    int dp[7001][2];
    set<int> now; 
    int solve(int pos,int f,int a ,int b,int x){
     //   cout<<pos<<" "<<f<<endl;
        
         if(pos == x)
            return 0;
        
        if( pos < 0 or now.count(pos) or pos>6000 )
            return 1e9;
        
        if(dp[pos][f]!=-1)
            return dp[pos][f];
        
        int &ans = dp[pos][f];
     
        if(f)
            ans = solve(pos+a,0,a,b,x)+1;
        else
            ans = min(solve(pos+a,0,a,b,x),solve(pos-b,1,a,b,x))+1;
        
        return ans;
    }
    int minimumJumps(vector<int>& forbidden, int a, int b, int x) {
        for(int x1 : forbidden)
            now.insert(x1);
        
        memset(dp,-1,sizeof(dp));
        
        int ans = solve(0,0,a,b,x);
        if(ans>1e9)
            return -1;
        return ans;
    }
};

One which gives AC

class Solution {
public:
   
    int dp[7001][2];
    set<int> now; 
    int solve(int pos,int f,int a ,int b,int x){
     //   cout<<pos<<" "<<f<<endl;
        
         if(pos == x)
            return 0;
        
        if( pos < 0 or now.count(pos) or pos>6000 )
            return 1e9;
        
        if(dp[pos][f]!=-1)
            return dp[pos][f];
        
        int &ans = dp[pos][f];
     
        ans = solve(pos+a,0,a,b,x)+1;
        if(!f)
            ans = min(ans,solve(pos-b,1,a,b,x)+1);
        
        return ans;
    }
    int minimumJumps(vector<int>& forbidden, int a, int b, int x) {
        for(int x1 : forbidden)
            now.insert(x1);
        
        memset(dp,-1,sizeof(dp));
        
        int ans = solve(0,0,a,b,x);
        if(ans>1e9)
            return -1;
        return ans;
    }
};

The difference

        //RE if I do this.
        int &ans = dp[pos][f];
        if(f)
            ans = solve(pos+a,0,a,b,x)+1;
        else
            ans = min(solve(pos+a,0,a,b,x),solve(pos-b,1,a,b,x))+1;

        //AC if I do this.
        int &ans = dp[pos][f];
        ans = solve(pos+a,0,a,b,x)+1;
        if(!f)
            ans = min(ans,solve(pos-b,1,a,b,x)+1);

Thanks!

Rev.	By	When	Δ	Comment
en3	Codeforcer	2021-05-25 11:46:18	2	Tiny change: ' I do this.\n ' -> ' I do this\n '
en2	Codeforcer	2021-05-25 11:31:24	70
en1	Codeforcer	2021-05-25 11:24:47	2704	(published)

Rev.

Lang.

When

Comment

en3

Codeforcer

2021-05-25 11:46:18

Tiny change: ' I do this.\n ' -> ' I do this\n '

en2

Codeforcer

2021-05-25 11:31:24

en1

Codeforcer

2021-05-25 11:24:47

2704

(published)

History