Calculate the number of way to reach at the end of array , if in each move , we are allowed to jump by 1 or 3 steps ?

Question

You always start from index "1" , you have to reach index "N".

 

Example : N = 4 .

Output :     2

Way-1 : 1-->2-->3-->4

Way-2 : 1-->4

Answer 1

We can use straightforward dynamic programming . 

Let dp[i] be the number of ways to reach index 'i' of the array . 

dp[1]=1 , dp[2] = 1 , dp[3] = 1 , dp[4] = 2 will be Base cases.

If you are at index 'i' , you can reach it , either from index 'i-1' or index 'i-3' ,  so dp[i] = dp[i-1] + dp[i-3] . 

Recurrence relation has been formed and we are done! Voial !

O(N) 

Code : 

#include<bits/stdc++.h>
using namespace std ; 
typedef long long int ll ; 
#define rep(i, l, r) for ((i) = (l); (i) <=(r); (i)++)
#define rep1(i, r, l) for ((i) = (r); (i) >=(l); (i)--)
int main()
{
    ll n ; 
    cin>>n; 
    ll dp[n+3]; 
    ll i ; 
    dp[1]=1;
    dp[2]=1;
    dp[3]=1;  
    dp[4]=2 ; 
    rep(i,5,n)
    {
        dp[i] = dp[i-3] + dp[i-1] ; 
    }
    cout<<dp[n]; 
    
    
    return 0 ; 
}