# Long jumps – Dp problem in C++

Now we will be going to solve a dynamic programming problem Long jumps in C++.

### Problem description

A person is currently standing on point 0 in the 1-D array and jumps to reach point N. For integers A and B, He can jump minimum A points and maximum B points. Given three integers N,A,B (1<=A<=B<=N) . Find the number of ways a person standing on point 0 can reach point N (modulo 1e9+7).

Constraints:

1<= N <=200000

Example

`N=6 A=2 B=4`

Output

`4`

#### Approach

It is a dp problem Let dp[i] be the corresponding answer for point i. We can simply observe that for point i, points i-a, i-a-1….i-b will contribute to the answer. So dp[i] = dp[i-a]+dp[i-a-1]…dp[i-b]. We will iterate i from 1 to n to get our corresponding answer. Its time complexity will be O(n^2) Since constraints on N, A, and B are large, the above solution may give Time Limit Exceeded. To calculate dp[i] fast, we can maintain a variable temp which stores value of dp[i-a]+dp[i-a-1]…dp[i-b], and everytime when we increase i, we will subtract dp[i-b-1] and add dp[i-a] to temp.

#### Implementation

```#include<bits/stdc++.h>
using namespace std;
#define mod 1000000007
int main(){
ios::sync_with_stdio(0);cin.tie(0);
int n,a,b,temp=0;
cin>>n>>a>>b;
vector<int>dp(n+1);
dp=1;
for(int i=1;i<=n;++i){
if(i-a<0) continue;
temp=(temp+dp[i-a])%mod;
if(i-b-1>=0) temp=(temp-dp[i-b-1]+mod)%mod;
dp[i]=temp;
}
cout<<dp[n];
}
```

Sample case

For given values, N=6, A=2, B=4 it means he can take jumps of 2, 3, and 4 points the answer will be 4. The 4 ways are : 0->2->4->6 , 0->2->6 , 0->3->6 , 0->4->6

Time complexity – O(n) And Space complexity – O(n).