1654. Minimum Jumps to Reach Home
A certain bug's home is on the x-axis at position x
. Help them get there from position 0
.
The bug jumps according to the following rules:
- It can jump exactly
a
positions forward (to the right). - It can jump exactly
b
positions backward (to the left). - It cannot jump backward twice in a row.
- It cannot jump to any
forbidden
positions.
The bug may jump forward beyond its home, but it cannot jump to positions numbered with negative integers.
Given an array of integers forbidden
, where forbidden[i]
means that the bug cannot jump to the position forbidden[i]
, and integers a
, b
, and x
, return the minimum number of jumps needed for the bug to reach its home. If there is no possible sequence of jumps that lands the bug on position x
, return -1.
Solution of Minimum Jumps to Reach Home-
int dp[6002][2];int solve(int pos,int t,int a,int b,int x){ if(pos==x) return 0; if(pos<0||pos>=6001||dp[pos][t]==-2) return 1e5; if(dp[pos][t]!=-1) return dp[pos][t]; dp[pos][t]=1+solve(pos+a,0,a,b,x); if(t==0) dp[pos][t]=min(dp[pos][t],1+solve(pos-b,1,a,b,x)); return dp[pos][t]; }
class Solution {public: int minimumJumps(vector<int>& forbidden, int a, int b, int x) { memset(dp,-1,sizeof(dp)); for(auto u:forbidden) dp[u][0]=-2,dp[u][1]=-2; int ans=solve(0,0,a,b,x); if(ans>=1e5) return -1; else return ans; }};
No comments:
Post a Comment