Memoization and RE - Codeforces

№	Пользователь	Рейтинг
1	tourist	4009
2	jiangly	3823
3	Benq	3738
4	Radewoosh	3633
5	jqdai0815	3620
6	orzdevinwang	3529
7	ecnerwala	3446
8	Um_nik	3396
9	ksun48	3390
10	gamegame	3386

№	Пользователь	Вклад
1	cry	167
2	maomao90	163
2	Um_nik	163
4	atcoder_official	161
5	adamant	159
6	-is-this-fft-	158
7	awoo	157
8	TheScrasse	154
9	nor	153
9	Dominater069	153

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.	Кто	Когда	Δ	Комментарий
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.

Язык

Кто

Когда

Комментарий

en3