Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- class Solution {
- public:
- set<int>s;
- vector<vector<long long>>dp;
- long long dfs(int cur,int a, int b, int x,int bcnt){
- if(cur==x)
- return 0;
- if(cur<0 or s.count(cur) or bcnt<0 or (bcnt>0 and cur-b>x) )
- return INT_MAX;
- long long &ans = dp[cur][bcnt];
- if(ans!=-1)
- return ans;
- dp[cur][bcnt]=INT_MAX;
- long long ans1= 1 + dfs(cur+a,a,b,x,1);
- long long ans2 = 1+ dfs(cur-b,a,b,x,bcnt-1);
- return dp[cur][bcnt] = min({ans1,ans2});
- }
- int minimumJumps(vector<int>& forbidden, int a, int b, int x) {
- for(auto &x:forbidden)
- s.insert(x);
- dp=vector<vector<long long>>(x+a+b,vector<long long>(3,-1LL));
- long long ans = dfs(0,a,b,x,1);
- if(ans>=INT_MAX)
- return -1;
- return ans;
- }
- };
Add Comment
Please, Sign In to add comment