Link: Count number of hops | Practice | GeeksforGeeks
This is the link to the problem. I am not getting why we cannot think this problem as a classical coin change dp problem where we have 1,2,3 as the changes available and N as the sum .
The answers are tribonacci numbers.
T(n) = T(n-1) + T(n-2) + T(n-3)
starting from T(0) = 1 ; T(1) = 1 ; T(2) = 2
I don’t know the classical coin problem, but here the answers are tribonacci numbers because the number of ways to reach the nth step will be the sum of the ways to reach the n-1th, n-2th, and n-3th steps which is basically a dp.