akashtadwai

Min Jumps to Reach Home

Oct 13th, 2021 (edited)
404
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.87 KB | None | 0 0
  1. class Solution {
  2. public:
  3.     set<int>s;
  4.    vector<vector<long long>>dp;
  5.     long long dfs(int cur,int a, int b, int x,int bcnt){
  6.         if(cur==x)
  7.             return 0;
  8.         if(cur<0 or s.count(cur) or bcnt<0 or (bcnt>0 and cur-b>x) )
  9.                 return INT_MAX;
  10.         long long &ans = dp[cur][bcnt];
  11.         if(ans!=-1)
  12.                 return ans;
  13.         dp[cur][bcnt]=INT_MAX;
  14.         long long ans1= 1 + dfs(cur+a,a,b,x,1);
  15.         long long ans2 = 1+ dfs(cur-b,a,b,x,bcnt-1);
  16.         return dp[cur][bcnt] = min({ans1,ans2});
  17.     }
  18.     int minimumJumps(vector<int>& forbidden, int a, int b, int x) {
  19.         for(auto &x:forbidden)
  20.                 s.insert(x);
  21.         dp=vector<vector<long long>>(x+a+b,vector<long long>(3,-1LL));
  22.        long long ans =  dfs(0,a,b,x,1);
  23.         if(ans>=INT_MAX)
  24.                 return -1;
  25.         return ans;
  26.     }
  27. };
Add Comment
Please, Sign In to add comment