- Arrays, Dynamic Programming, Mathematical

Count ways to reach the Nth station

Count ways to reach the Nth stationGiven N stations and three trains A, B, and C such that train A stops at every station, train B stops at every second station, and train C stops at every third station, the task is to find the number of ways to reach the Nth station can be reached from station 1.Examples:Input: N = 4Output: 3Explanation:Below are the ways of reaching station 4 from station 1 as follows:Take train A at station 1 and continue to station 4 using only train A as (A → A → A → A).Take train B at station 1, stop at station 3 and take train A from station 3 to 4 as (B→ . → A).Take train C from station 1 and stop at station 4(C→ .)Therefore, the total number of ways to reach station 4 from station 1 is 3.Input: N = 15Output: 338Approach: The given problem can be solved using the following observations:Train A can be used to reach station X only if train A reaches X – 1.Train B can be used to reach station X only if train B reaches X – 2.Train C can be used to reach station X only if train C reaches X – 3.Therefore, from the above observations, the idea is to use the concept of Dynamic Programming. Follow the steps given below to solve the problem:Initialize a 2D array DP such that:DP[i][1] stores the number of ways to reach station i using train A.DP[i][2] stores the number of ways to reach station i using train B.DP[i][3] stores the number of ways to reach station i using train C.DP[i][4] stores the number of ways to reach station i using trains A, B, or C.There is only one way of reaching station 1. Therefore, update the value of DP[1][1], DP[1][2], DP[1][3], DP[1][4] as 1.Using the above observations, update the value of each state by iterating the loop as follows:DP[i][1] = DP[i-1][4]DP[i][2] = DP[i-2][4]DP[i][3] = DP[i-3][4]DP[i][4] = DP[i][1] + DP[i][2] + DP[i][3]After completing the above steps, print the value of DP[N][4] as the result.Below is the implementation of the above approach:C++#include using namespace std;int numberOfWays(int N){        int DP[N + 1][5];        memset(DP, 0, sizeof(DP));        DP[1][1] = 1;    DP[1][2] = 1;    DP[1][3] = 1;    DP[1][4] = 1;            for (int i = 2; i 0 && DP[i – 1][1] > 0)            DP[i][1] = DP[i – 1][4];                        if (i – 2 > 0 && DP[i – 2][2] > 0)            DP[i][2] = DP[i – 2][4];                        if (i – 3 > 0 && DP[i – 3][3] > 0)            DP[i][3] = DP[i – 3][4];                        DP[i][4] = (DP[i][1] + DP[i][2]                    + DP[i][3]);    }        return DP[N][4];}int main(){    int N = 15;    cout 0 and DP[i – 1][1] > 0):            DP[i][1] = DP[i – 1][4]                        if (i – 2 > 0 and DP[i – 2][2] > 0):            DP[i][2] = DP[i – 2][4]                        if (i – 3 > 0 and DP[i – 3][3] > 0):            DP[i][3] = DP[i – 3][4]                        DP[i][4] = (DP[i][1] + DP[i][2] + DP[i][3])        return DP[N][4]if __name__ == ‘__main__’:         N = 15         print(numberOfWays(N))Output: 338Time Complexity: O(N)Auxiliary Space: O(N)Attention reader! Don’t stop learning now. Get hold of all the important mathematical concepts for competitive programming with the Essential Maths for CP Course at a student-friendly price. To complete your preparation from learning a language to DS Algo and many more,  please refer Complete Interview Preparation Course.