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).
Leave a Reply