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[0]=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).