Count number of hops

A frog jumps either 1, 2, or 3 steps to go to the top. In how many ways can it reach the top. As the answer will be large find the answer modulo 1000000007.

• Time : O(n)
• Space : O(n)

class Solution {
    vector<int> dp;
    int mod = 1e9 + 7;
    int helper(int n) {
        if(n < 0) return 0;
        if(dp[n] != -1) return dp[n];
        dp[n] = (((helper(n - 1) + helper(n - 2)) % mod) + helper(n - 3)) % mod;
        return dp[n];
    }
public:
    //Function to count the number of ways in which frog can reach the top.
    long long countWays(int n) {
        dp = vector<int>(n + 1, -1);
        dp[0] = 1;
        return helper(n);
    }
};

• Time : O(n)
• Space : O(1)

class Solution {
    int mod = 1e9 + 7;
public:
    //Function to count the number of ways in which frog can reach the top.
    long long countWays(int n) {
        if(n <= 2) return n;
        int a = 1, b = 1, c = 2;
        for(int i = 3; i <= n; i++) {
            int nc = (((a + b) % mod) + c) % mod;
            a = b;
            b = c;
            c = nc;
        }
        return c;
    }
};