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.
Example 1:
Input:
N = 1
Output: 1
Example 2:
Input:
N = 4
Output: 7
Explanation:Below are the 7 ways to reach
4
1 step + 1 step + 1 step + 1 step
1 step + 2 step + 1 step
2 step + 1 step + 1 step
1 step + 1 step + 2 step
2 step + 2 step
3 step + 1 step
1 step + 3 step
Your Task:
Your task is to complete the function countWays() which takes 1 argument(N) and returns the answer%(10^9 + 7).
Expected Time Complexity: O(N).
Expected Auxiliary Space: O(1).
Constraints:
1 ≤ N ≤ 10^{5}

Source: geeksforgeeks | Difficulty: EASY
Tags: Dynamic programming

Starter code: #User function Template for python3

class Solution:
    #Function to count the number of ways in which frog can reach the top.
    def countWays(self,n):
        
        # code here

Solutions:
class Solution:

	def countWays(self, n):
		s1 = 1
		s2 = 2
		s3 = 4
		if n == 1:
			return 1
		elif n == 2:
			return 2
		elif n == 3:
			return 4
		else:
			for i in range(4, n + 1):
				ways = (s1 + s2 + s3) % 1000000007
				s1 = s2
				s2 = s3
				s3 = ways
			return ways


class Solution:

	def countWays(self, n):
		l = {}
		l[0] = 1
		l[1] = 1
		l[2] = 2
		for i in range(3, n + 1):
			l[i] = l[i - 1] + l[i - 2] + l[i - 3]
		return l[n] % (10 ** 9 + 7)


class Solution:

	def countWays(self, n):
		MOD = 1000000007
		dp = [1, 2, 4]
		if n < 4:
			return dp[n - 1]
		for i in range(4, n + 1):
			count = (dp[0] + dp[1] + dp[2]) % MOD
			dp[0] = dp[1]
			dp[1] = dp[2]
			dp[2] = count
		return dp[-1]


class Solution:

	def countWays(self, n):
		dp = {}
		mm = 1000000007
		dp[0] = 1
		dp[1] = 1
		dp[2] = 2
		for i in range(3, n + 1):
			dp[i] = dp[i - 1] % mm + dp[i - 2] % mm + dp[i - 3] % mm
		return dp[n] % mm


class Solution:

	def countWays(self, n):
		dp = [-1] * (n + 1)

		def steps(n):
			if n == 1:
				dp[n] = 1
				return 1
			if n == 2:
				dp[n] = 2
				return 2
			if n == 3:
				dp[n] = 4
				return 4
			if dp[n] != -1:
				return dp[n]
			dp[n] = steps(n - 1) + steps(n - 2) + steps(n - 3)
			return dp[n]
		steps(n)
		return dp[-1] % (10 ** 9 + 7)


class Solution:

	def countWays(self, n):
		s = 0
		if n == 0:
			return 1
		elif n == 1:
			return 1
		elif n == 2:
			return 2
		else:
			a = 1
			b = 1
			c = 2
			for i in range(0, n - 2):
				s = a + b + c
				a = b
				b = c
				c = s
		return s % (10 ** 9 + 7)


class Solution:

	def countWays(self, n):
		if n == 1:
			return 1
		if n == 2:
			return 2
		if n == 3:
			return 4
		a = 1
		b = 2
		c = 4
		for i in range(4, n + 1):
			d = a + b + c
			a = b
			b = c
			c = d
		return c % (10 ** 9 + 7)


class Solution:

	def countWays(self, n):
		if n == 1:
			return 1
		if n == 2:
			return 2
		if n == 3:
			return 4
		n1 = 1
		n2 = 2
		n3 = 4
		for i in range(4, n + 1):
			temp = n1 + n2 + n3
			n1 = n2
			n2 = n3
			n3 = temp
		return n3 % (10 ** 9 + 7)


class Solution:

	def countWays(self, n):
		if n == 1:
			return 1
		if n == 2:
			return 2
		if n == 3:
			return 4
		(one, two, three) = (1, 2, 4)
		for i in range(4, n + 1):
			temp = (one + two + three) % 1000000007
			one = two
			two = three
			three = temp
		return three


data = {0: 1, 1: 1, 2: 2}

class Solution:

	def countWays(self, n):

		def hops(m):
			if m in data:
				return data[m]
			data[m] = hops(m - 3) + hops(m - 2) + hops(m - 1)
			return data[m]
		return hops(n) % (10 ** 9 + 7)


class Solution:

	def fun(self, n, dp):
		if n == 0:
			return 1
		elif n < 0:
			return 0
		if dp[n] != -1:
			return dp[n] % (10 ** 9 + 7)
		dp[n] = (self.fun(n - 1, dp) % (10 ** 9 + 7) + self.fun(n - 2, dp) % (10 ** 9 + 7) + self.fun(n - 3, dp) % (10 ** 9 + 7)) % (10 ** 9 + 7)
		return dp[n] % (10 ** 9 + 7)

	def countWays(self, n):
		dp = [-1 for i in range(10 ** 5 + 1)]
		return self.fun(n, dp)


class Solution:

	def countWays(self, n):
		if n == 0:
			return 0
		dp = [-1] * n
		return self.numberWays(n, dp) % 1000000007

	def numberWays(self, n, dp):
		num = 0
		if n <= 0:
			return 0
		if dp[n - 1] != -1:
			return dp[n - 1]
		for i in range(1, 4):
			if n == i:
				num += 1
			else:
				num += self.numberWays(n - i, dp)
		dp[n - 1] = num
		return num


class Solution:

	def countWays(self, n):
		if n == 1:
			return 1
		elif n == 2:
			return 2
		elif n == 3:
			return 4
		else:
			(p, q, r) = (1, 2, 4)
			for i in range(3, n):
				temp = (p + q + r) % 1000000007
				p = q
				q = r
				r = temp
			return temp


class Solution:

	def countWays(self, n):
		if n == 1:
			return 1
		elif n == 2:
			return 2
		elif n == 3:
			return 4
		(a, b, c, d) = (1, 2, 4, 0)
		for i in range(4, n + 1):
			d = (a + b + c) % 1000000007
			a = b
			b = c
			c = d
		return d


class Solution:

	def countWays(self, n):
		if n == 1:
			return 1
		if n == 2:
			return 2
		if n == 3:
			return 4
		if n == 4:
			return 7
		l = [1, 2, 4, 7]
		for i in range(4, n):
			l.append(2 * l[i - 1] - l[i - 4])
		return l[i] % 1000000007


class Solution:

	def countWays(self, n):
		if n == 1:
			return 1
		if n == 2:
			return 2
		if n == 3:
			return 4
		else:
			a = 1
			b = 2
			c = 4
			s = 0
			for i in range(4, n + 1):
				s = a + b + c
				a = b
				b = c
				c = s
			else:
				return s % 1000000007


class Solution:

	def countWays(self, n):
		arr = [1, 2, 4]
		if n in range(1, 4):
			return arr[n - 1]
		for i in range(4, n + 1):
			newval = arr[0] + arr[1] + arr[2]
			newarr = []
			newarr.append(arr[1])
			newarr.append(arr[2])
			newarr.append(newval)
			arr = newarr
		return arr[-1] % 1000000007


class Solution:

	def countWays(self, n):

		def go(x):
			if x >= n:
				if x == n:
					return 1
				return 0
			if dp[x] != -1:
				return dp[x]
			ans = (go(x + 1) + go(x + 2) + go(x + 3)) % (10 ** 9 + 7)
			dp[x] = ans
			return ans
		dp = [-1] * (n + 3)
		return go(0)


class Solution:

	def countWays(self, n):
		l = [1, 2, 4]
		if n in range(1, 4):
			return l[n - 1]
		for i in range(4, n + 1):
			temp = l[0] + l[1] + l[2]
			l[0] = l[1]
			l[1] = l[2]
			l[2] = temp
		return l[2] % 1000000007


class Solution:

	def countWays(self, n):
		d = [1, 1, 2]
		i = 3
		while i <= n:
			j = sum(d)
			d[i % 3] = j
			i += 1
		return d[n % 3] % (10 ** 9 + 7)


class Solution:

	def countWays(self, n):
		if n < 3:
			return n
		dp = [0 for i in range(n + 1)]
		dp[0] = 1
		dp[1] = 1
		dp[2] = 2
		dp[3] = 4
		maxi = pow(10, 9) + 7
		for i in range(4, n + 1):
			dp[i] = ((dp[i - 1] + dp[i - 2]) % maxi + dp[i - 3]) % maxi
		return dp[-1] % maxi


class Solution:

	def countWays(self, n):
		(a, b, c) = (1, 2, 4)
		m = 10 ** 9 + 7
		if n == 1:
			return a
		if n == 2:
			return b
		if n == 3:
			return c
		ans = 0
		for i in range(4, n + 1):
			ans = (a + b + c) % m
			a = b
			b = c
			c = ans
		return ans


class Solution:

	def countWays(self, n):

		def ways(ind, dp):
			if ind < 0:
				return 0
			if ind == 0:
				return 1
			if dp[ind] != -1:
				return dp[ind]
			fr = ways(ind - 1, dp) % 1000000007
			se = ways(ind - 2, dp) % 1000000007
			th = ways(ind - 3, dp) % 1000000007
			dp[ind] = (fr + se + th) % 1000000007
			return dp[ind]
		dp = [-1 for i in range(n + 1)]
		return ways(n, dp)


class Solution:

	def countWays(self, n):
		MOD = 10 ** 9 + 7
		dp = [0] * (n + 1)
		dp[0] = 1
		if n >= 1:
			dp[1] = 1
		if n >= 2:
			dp[2] = 2
		for i in range(3, n + 1):
			dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3]
		return dp[n] % MOD


class Solution:

	def countWays(self, n):

		def getValue(n):
			if n == 1:
				return 1
			if n == 2:
				return 2
			if n == 3:
				return 4
			if dp[n] != -1:
				return dp[n]
			val1 = getValue(n - 1)
			val2 = getValue(n - 2)
			val3 = getValue(n - 3)
			dp[n] = val1 + val2 + val3
			return dp[n]
		dp = [-1 for i in range(n + 1)]
		return getValue(n) % 1000000007


class Solution:

	def countWays(self, n):
		if n == 1:
			return 1
		if n == 2:
			return 2
		dp = [1] * (n + 1)
		dp[2] = 2
		for i in range(3, n + 1):
			dp[i] = (dp[i - 3] + dp[i - 2] + dp[i - 1]) % 1000000007
		return dp[n]


class Solution:

	def countWays(self, n):
		if n < 3:
			return n
		dp = [1] * (n + 1)
		dp[2] = 2
		for i in range(3, n + 1):
			dp[i] = (dp[i - 1] + dp[i - 2] + dp[i - 3]) % 1000000007
		return dp[n] % 1000000007
11111
1112
1121
1211
2111
122
221
212
113
131
311
32
23


class Solution:

	def countWays(self, n):
		count = [0] * (n + 1)
		count[0] = 1
		if n >= 1:
			count[1] = 1
		if n >= 2:
			count[2] = 2
		for i in range(3, n + 1):
			count[i] = count[i - 1] + count[i - 2] + count[i - 3]
		return count[n] % 1000000007


class Solution:

	def countWays(self, n):
		if n == 1:
			return 1
		if n == 2:
			return 2
		if n == 3:
			return 4
		(n1, n2, n3) = (1, 2, 4)
		mod = 1000000007
		for i in range(4, n + 1):
			(n1, n2, n3) = (n2, n3, n1 + n2 + n3)
			(n1, n2, n3) = (n1 % mod, n2 % mod, n3 % mod)
		return n3


class Solution:

	def countWays(self, n):
		mod = 1000000007
		t = [-1 for i in range(n + 1)]

		def solve(n):
			if n == 0 or n == 1:
				return 1
			if n < 0:
				return 0
			if t[n] != -1:
				return t[n]
			a = solve(n - 1) % mod
			b = solve(n - 2) % mod
			c = solve(n - 3) % mod
			ans = (a + b + c) % mod
			t[n] = ans % mod
			return t[n]
		return solve(n)


class Solution:

	def countWays(self, n):
		mod = 1000000007
		if n == 1:
			return 1
		if n == 2:
			return 2
		t1 = 1
		t2 = 2
		t3 = 4
		for i in range(4, n + 1):
			t = t3
			t3 += t2 + t1
			t1 = t2
			t2 = t
		return t3 % mod


class Solution:

	def countWays(self, n):
		a = []
		a.append(1)
		a.append(1)
		a.append(2)
		for i in range(3, n + 1):
			a.append(a[i - 1] + a[i - 2] + a[i - 3])
			a[i] %= 1000000007
		return a[n]


class Solution:

	def countWays(self, n, memo=dict()):
		if n == 0:
			return 1
		if n < 0:
			return 0
		if n in memo:
			return memo[n]
		ans1 = self.countWays(n - 1, memo)
		ans2 = self.countWays(n - 2, memo)
		ans3 = self.countWays(n - 3, memo)
		totalAns = ans1 + ans2 + ans3
		memo[n] = totalAns % 1000000007
		return memo[n]


class Solution:

	def countWays(self, n):
		if n == 1:
			return 1
		elif n == 2:
			return 2
		elif n == 3:
			return 4
		dp = [1, 2, 4]
		i = 3
		for i in range(3, n):
			dp.append(sum(dp[i - 3:i]))
		return dp[n - 1] % 1000000007


class Solution:

	def countWays(self, n):
		l = [0] * (n + 1)
		for i in range(n + 1):
			if i == 0:
				l[i] = 1
			elif i == 1:
				l[i] = 1
			elif i == 2:
				l[i] = 2
			else:
				l[i] = l[i - 3] + l[i - 2] + l[i - 1]
		return l[n] % 1000000007


class Solution:

	def countWays(self, n):
		dp = [-1] * (n + 1)

		def ways(n):
			if n < 0:
				return 0
			if n == 0 or n == 1:
				return 1
			if dp[n] != -1:
				return dp[n] % (10 ** 9 + 7)
			dp[n] = (ways(n - 3) + ways(n - 2) + ways(n - 1)) % (10 ** 9 + 7)
			return dp[n] % (10 ** 9 + 7)
		return ways(n) % (10 ** 9 + 7)