There are n stairs, a person standing at the bottom wants to reach the top. The person can climb either 1 stair or 2 stairs at a time. Count the number of ways, the person can reach the top (order does matter).
Example 1:
Input:
n = 4
Output: 5
Explanation:
You can reach 4th stair in 5 ways. 
Way 1: Climb 2 stairs at a time. 
Way 2: Climb 1 stair at a time.
Way 3: Climb 2 stairs, then 1 stair
and then 1 stair.
Way 4: Climb 1 stair, then 2 stairs
then 1 stair.
Way 5: Climb 1 stair, then 1 stair and
then 2 stairs.
Example 2:
Input:
n = 10
Output: 89 
Explanation: 
There are 89 ways to reach the 10th stair.
Your Task:
Complete the function countWays() which takes the top stair number m as input parameters and returns the answer % 10^9+7.
Expected Time Complexity : O(n)
Expected Auxiliary Space: O(1)
Constraints:
1 ≤ n ≤ 10^{4}

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Dynamic programming

Amortized analysis

Mathematics

Starter code: #User function Template for python3



class Solution:

    #Function to count number of ways to reach the nth stair.

    def countWays(self,n):

        

        # code here

Solutions:
class Solution:

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

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


class Solution:

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


class Solution:

	def countWays(self, n):
		d = {}

		def dfs(n):
			if n not in d:
				if n <= 1:
					d[n] = 1
				else:
					d[n] = (dfs(n - 1) + dfs(n - 2)) % (10 ** 9 + 7)
			return d[n]
		return dfs(n)


class Solution:

	def countWays(self, n):
		if n == 1:
			return 1
		prev = 2
		prev2 = 1
		for i in range(2, n):
			cur = prev + prev2
			prev2 = prev
			prev = cur
		return prev % (10 ** 9 + 7)


class Solution:

	def countWays(self, n):
		ans = 1
		prev1 = 1
		prev2 = 1
		for i in range(2, n + 1):
			ans = prev1 + prev2
			prev2 = prev1
			prev1 = ans
		return ans % (10 ** 9 + 7)


class Solution:

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


class Solution:

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


class Solution:

	def countWays(self, n):
		if n <= 2:
			return n
		step1 = 1
		step2 = 2
		div = 10 ** 9 + 7
		for i in range(n - 2):
			ans = (step1 + step2) % div
			step1 = step2
			step2 = ans
		return step2


class Solution:

	def recCountWays(self, index, dp):
		if index <= 1:
			return 1
		if dp[index] != -1:
			return dp[index]
		downOneIndex = self.recCountWays(index - 1, dp)
		downTwoIndex = 0
		if index > 1:
			downTwoIndex = self.recCountWays(index - 2, dp)
		dp[index] = (downOneIndex + downTwoIndex) % (10 ** 9 + 7)
		return (downOneIndex + downTwoIndex) % (10 ** 9 + 7)

	def countWays(self, n):
		prev1 = 1
		prev = 1
		for index in range(n + 1):
			downOneIndex = prev
			downTwoIndex = 0
			if index > 1:
				downTwoIndex = prev1
			curr = (downOneIndex + downTwoIndex) % (10 ** 9 + 7)
			prev1 = prev
			prev = curr
		return prev


class Solution:

	def recCountWays(self, index, dp):
		if index <= 1:
			return 1
		if dp[index] != -1:
			return dp[index]
		downOneIndex = self.recCountWays(index - 1, dp)
		downTwoIndex = 0
		if index > 1:
			downTwoIndex = self.recCountWays(index - 2, dp)
		dp[index] = (downOneIndex + downTwoIndex) % (10 ** 9 + 7)
		return (downOneIndex + downTwoIndex) % (10 ** 9 + 7)

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


class Solution:

	def sol(self, n):
		m = 1000000007
		prev2 = 1
		prev = 1
		for i in range(2, n + 1):
			curr = (prev + prev2) % m
			prev2 = prev
			prev = curr
		return prev

	def countWays(self, n):
		return self.sol(n)


class Solution:

	def sol(self, dp, n):
		m = 1000000007
		dp[0] = 1
		dp[1] = 1
		for i in range(2, n + 1):
			dp[i] = (dp[i - 1] + dp[i - 2]) % m
		return dp[len(dp) - 1]

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


class Solution:

	def sol(self, idx, dp):
		m = 1000000007
		if idx <= 1:
			dp[idx] = 1
		if dp[idx] != -1:
			return dp[idx]
		dp[idx] = (self.sol(idx - 1, dp) + self.sol(idx - 2, dp)) % m
		return dp[idx]

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


class Solution:

	def countWays(self, n):
		if n == 1:
			return 1
		prev2 = 1
		prev1 = 2
		for i in range(n - 2):
			s = prev1 + prev2
			prev2 = prev1
			prev1 = s
		return prev1 % 1000000007


mod = 10 ** 9 + 7

class Solution:

	def countWays(self, n):
		if n is 1:
			return 1
		prev2 = 1
		prev1 = 2
		for i in range(2, n):
			cur = (prev2 + prev1) % mod
			prev2 = prev1
			prev1 = cur
		return prev1


mod = 10 ** 9 + 7

class Solution:

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

		def memo(n):
			if n == 0 or n == 1:
				return 1
			if dp[n] != -1:
				return dp[n]
			dp[n] = (memo(n - 1) + memo(n - 2)) % mod
			return dp[n] % mod
		return memo(n)


class Solution:

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


class Solution:

	def countWays(self, n):
		mod = 10 ** 9 + 7
		arr = [1, 1]
		for i in range(2, n + 1):
			ele = (arr[i - 1] % mod + arr[i - 2] % mod) % mod
			arr.append(ele)
		return arr[n]


mod = 10 ** 9 + 7

class Solution:

	def helper(self, n, i, dp):
		if i == n:
			return 1
		if i > n:
			return 0
		if dp[i + 1] == -1:
			l = self.helper(n, i + 1, dp)
			dp[i + 1] = l
		else:
			l = dp[i + 1]
		if dp[i + 2] == -1:
			k = self.helper(n, i + 2, dp)
			dp[i + 2] = l
		else:
			k = dp[i + 2]
		ans = k + l
		dp[i] = ans
		return ans

	def countWays(self, n):
		dp = [-1 for _ in range(n + 2)]
		ans = self.helper(n, 0, dp) % mod
		return ans


class Solution:

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

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


class Solution:

	def countWays(self, n):
		dp = []
		ans = 0
		for i in range(n + 1):
			if i == 0 or i == 1:
				dp.append(1)
				continue
			dp.append(dp[i - 1] + dp[i - 2])
		return dp[-1] % (pow(10, 9) + 7)


class Solution:

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

		def solve(n, dp):
			if n <= 2:
				dp[n] = n
				return dp[n]
			if dp[n] != -1:
				return dp[n]
			dp[n] = (solve(n - 1, dp) % mod + solve(n - 2, dp) % mod) % mod
			return dp[n]
		return solve(n, dp)


class Solution:

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

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


class Solution:

	def __init__(self):
		self.MODULAR_CONSTANT = 10 ** 9 + 7

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

	def helper(self, dp, n):
		if n == 0 or n == 1:
			dp[n] = 1
			return dp[n] % self.MODULAR_CONSTANT
		elif n in dp:
			return dp[n] % self.MODULAR_CONSTANT
		else:
			dp[n] = (self.helper(dp, n - 1) + self.helper(dp, n - 2)) % self.MODULAR_CONSTANT
			return dp[n] % self.MODULAR_CONSTANT


class Solution:

	def countWays(self, n):
		if n == 0 or n == 1:
			return 1
		else:
			arr = [1] * (n + 1)
			for i in range(2, n + 1):
				arr[i] = arr[i - 1] + arr[i - 2]
		return arr[-1] % (10 ** 9 + 7)


import sys
sys.setrecursionlimit(10 ** 4)

class Solution:

	def countWays(self, n):
		i = 0
		count = 0
		flag = 0
		mem = n * [-1]
		return self.helper(n, i, count, mem) % (10 ** 9 + 7)

	def helper(self, n, i, count, mem):
		if i == n:
			count = count + 1
			return count
		elif i > n:
			return 0
		if mem[i] != -1:
			return mem[i]
		else:
			sum = (self.helper(n, i + 1, count, mem) + self.helper(n, i + 2, count, mem)) % (10 ** 9 + 7)
			mem[i] = sum
			return sum


class Solution:

	def countWays(self, n):
		(first, second) = (1, 1)
		for i in range(2, n + 1):
			(first, second) = (second, first + second)
		return second % (10 ** 9 + 7)


class Solution:

	def countWays(self, n):
		cache = {}

		def count(i):
			if i in cache:
				return cache[i]
			if i <= 2:
				return i
			res = count(i - 1) + count(i - 2)
			cache[i] = res
			return res
		return count(n) % 1000000007


mod = 1000000000.0 + 7

class Solution:

	def countWays(self, n):
		prev2 = 1
		prev1 = 1
		for i in range(2, n + 1):
			cur = (prev2 + prev1) % mod
			prev2 = prev1
			prev1 = cur
		return int(prev1)


class Solution:

	def countWays(self, n):
		_m = 10 ** 9 + 7
		if n <= 1:
			return n
		_p1 = 1
		_p2 = 1
		for _ in range(2, n + 1):
			_c = _p1 + _p2
			_p2 = _p1
			_p1 = _c
		return _p1 % _m


from functools import lru_cache

class Solution:

	@lru_cache()
	def recur(self, n):
		if n == 0 or n == 1:
			return 1
		return self.recur(n - 1) + self.recur(n - 2)

	def countWays(self, n):
		cache = {}
		ans = self.recur(n)
		return ans % (10 ** 9 + 7)


class Solution:

	def recur(self, n, cache):
		if n in cache:
			return cache[n]
		if n == 0 or n == 1:
			cache[n] = 1
			return cache[n]
		cache[n] = self.recur(n - 1, cache) + self.recur(n - 2, cache)
		return cache[n]

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


class Solution:

	def solve(self, n, dp):
		if n < 0:
			return 0
		if dp[n] != -1:
			return dp[n]
		if n >= 2:
			dp[n] = self.solve(n - 1, dp) + self.solve(n - 2, dp)
		return dp[n]

	def countWays(self, n):
		if n <= 2 and n >= 0:
			return n
		dp = [-1 for i in range(n + 1)]
		dp[1] = 1
		dp[2] = 2
		a = self.solve(n, dp)
		m = 1000000007
		return dp[n] % m


class Solution:

	def countWays(self, n):
		ways = [-1] * (n + 1)
		return self.totalWays(n, ways, n)

	def totalWays(self, i, ways, n):
		if i == 0:
			return 1
		elif i < 0:
			return 0
		elif ways[i] != -1:
			return ways[i]
		else:
			m = 10 ** 9 + 7
			ways[i] = (self.totalWays(i - 1, ways, n) % m + self.totalWays(i - 2, ways, n) % m) % m
			return ways[i]


class Solution:

	def countWays(self, n):
		f = 1
		s = 2
		if n == 1:
			return f
		m = 10 ** 9 + 7
		for i in range(3, n + 1):
			cur = (s % m + f % m) % m
			f = s
			s = cur
		return s


class Solution:

	def countWays(self, n):
		if n < 1:
			return 1
		count = [0 for _ in range(n + 1)]
		count[0] = count[1] = 1
		for stair in range(2, n + 1):
			for step in range(1, 3):
				count[stair] += count[stair - step]
				count[stair] %= 1000000007
		return count[n]


class Solution:

	def countWays(self, n):
		if n == 1:
			return 1
		elif n == 2:
			return 2
		l = []
		l.append(1)
		l.append(2)
		for i in range(2, n):
			l.append(l[i - 1] + l[i - 2])
		return l[-1] % (10 ** 9 + 7)


class Solution:

	def countWays(self, n):
		if n == 1:
			return 1
		if n == 2:
			return 2
		dp = []
		dp.append(1)
		dp.append(2)
		for i in range(2, n):
			dp.append(dp[i - 1] + dp[i - 2])
		return dp[-1] % (pow(10, 9) + 7)


class Solution:

	def countWays(self, n):
		(prev, prev2) = (1, 1)
		for i in range(1, n):
			curr = prev + prev2
			prev2 = prev
			prev = curr
		return prev % (10 ** 9 + 7)


class Solution:

	def driver(self, n):
		if not self.table[n - 1] == -1:
			return self.table[n - 1]
		else:
			ans = self.driver(n - 1) + self.driver(n - 2)
			self.table[n - 1] = ans
			return ans

	def countWays(self, n):
		self.table = [-1] * n
		if n > 0:
			self.table[0] = 1
		if n > 1:
			self.table[1] = 2
		return int(self.driver(n)) % (10 ** 9 + 7)


class Solution:

	def countWays(self, n):
		if n == 0 or n == 1:
			return 1
		dp = [0 for i in range(n + 1)]
		dp[1] = 1
		dp[0] = 1
		for i in range(1, n + 1):
			dp[i] = int((dp[i - 1] % (1000000000.0 + 7) + dp[i - 2] % (1000000000.0 + 7)) % (1000000000.0 + 7))
		return dp[n]


class Solution:

	def countWays(self, n):
		prev2 = 0
		prev1 = 1
		for i in range(1, n + 1):
			cur = (prev1 + prev2) % (10 ** 9 + 7)
			prev2 = prev1
			prev1 = cur
		return prev1


class Solution:

	def rec(self, i, dp):
		if i == -1:
			return 0
		if i == 0:
			return 1
		if dp[i] != -1:
			return dp[i]
		dp[i] = (self.rec(i - 1, dp) + self.rec(i - 2, dp)) % (10 ** 9 + 7)
		return dp[i]

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


class Solution:

	def countWays(self, n):
		a = 0
		b = 1
		for i in range(n):
			(a, b) = (b, (a + b) % (10 ** 9 + 7))
		return b


class Solution:

	def countWays(self, n):
		(one, two) = (1, 1)
		for i in range(n - 1):
			temp = one + two
			one = two
			two = temp
		return two % (10 ** 9 + 7)


class Solution:

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


mod = 1000000007

class Solution:

	def countWays(self, n):
		if n <= 1:
			return 1
		a = 1
		b = 1
		for i in range(2, n + 1):
			c = (a + b) % mod
			a = b
			b = c
		return c


class Solution:

	def countWays(self, n):
		one = 1
		two = 1
		mod = 1000000007
		for i in range(2, n + 1):
			(two, one) = (one + two, two)
		return two % mod


class Solution:

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


class Solution:

	def countWays(self, n):
		a = 1
		b = 2
		res = 0
		if n == 1 or n == 2:
			return n
		while n > 2:
			n -= 1
			res = (a + b) % (10 ** 9 + 7)
			a = b
			b = res
		return res % (10 ** 9 + 7)


class Solution:

	def countWays(self, n):
		req = n - 1
		(prev, cur) = (1, 1)
		tot = 2
		if n == 1:
			return 1
		if n == 2:
			return 2
		for i in range(req - 2):
			newstep = prev + cur
			prev = cur
			cur = newstep
			tot += newstep
			tot = tot % (pow(10, 9) + 7)
		return tot + 1


class Solution:

	def mul(self, A, B, MOD):
		K = len(A)
		C = [[0 for i in range(K)] for j in range(K)]
		for i in range(1, K):
			for j in range(1, K):
				for k in range(1, K):
					C[i][j] = (C[i][j] + A[i][k] * B[k][j]) % MOD
		return C

	def power(self, A, n):
		if n == 1:
			return A
		if n % 2 != 0:
			A = self.mul(A, self.power(A, n - 1), 1000000007)
		else:
			A = self.power(A, n // 2)
			A = self.mul(A, A, 1000000007)
		return A

	def countWays(self, n):
		F = [0 for i in range(3)]
		F[1] = 1
		F[2] = 2
		K = 2
		MOD = 1000000007
		C = [[0 for i in range(K + 1)] for j in range(K + 1)]
		for i in range(1, K):
			C[i][i + 1] = 1
		C[K][1] = 1
		C[K][2] = 1
		if n <= 2:
			return F[n]
		C = self.power(C, n - 1)
		result = 0
		for i in range(1, K + 1):
			result = (result + C[1][i] * F[i]) % MOD
		return result


class Solution:

	def countWays(self, n):
		dp = []
		mod = 1000000000 + 7
		dp.append(1)
		for i in range(1, n):
			dp.append((dp[i - 1] % mod + dp[i - 2] % mod) % mod)
		return dp[-1]


class Solution:

	def countWays(self, n):
		(one, two) = (1, 1)
		for i in range(n - 1):
			temp = one
			one = one + two
			two = temp
		return one % 1000000007


class Solution:

	def countWays(self, n):
		if n == 0 or n == 1:
			return 1
		else:
			prev = 1
			prev2 = 1
			for i in range(2, n + 1):
				cur_i = prev2 + prev
				prev2 = prev
				prev = cur_i
			return prev % (10 ** 9 + 7)


mod = 10 ** 9 + 7

class Solution:

	def helper(self, dp, n):
		if n == 2:
			return 2
		elif n == 1:
			return 1
		if n in dp:
			return dp[n]
		else:
			dp[n] = (self.helper(dp, n - 1) + self.helper(dp, n - 2)) % mod
			return dp[n]

	def countWays(self, n):
		dp = dict()
		return self.helper(dp, n)


class Solution:

	def countWays(self, n):
		fib1 = 1
		fib2 = 2
		if n == 1:
			return 1
		if n == 2:
			return 2
		total = 0
		for ctr in range(2, n):
			total = fib1 + fib2
			fib1 = fib2
			fib2 = total
		return total % (10 ** 9 + 7)


class Solution:
	c = 0
	dp = [-1] * 10000

	def gen(self, n, count):
		if count == n:
			return 1
		if count == n - 1:
			return 1
		if count < n and self.dp[count] != -1:
			return self.dp[count]
		l = self.gen(n, count + 1)
		r = self.gen(n, count + 2)
		self.dp[count] = l + r
		return l + r

	def countWays(self, n):
		if n == 1:
			return 1
		self.dp = [-1] * 10000
		self.gen(n, 0)
		suma = 0
		return self.dp[0] % (10 ** 9 + 7)


class Solution:

	def countWays(self, n):

		def fun(n):
			mod = 10 ** 9 + 7
			if n == 0:
				return 1
			if n == 1:
				return 1
			if arr[n] != -1:
				return arr[n] % mod
			else:
				arr[n] = (fun(n - 1) % mod + fun(n - 2) % mod) % mod
			return arr[n]
		arr = []
		for i in range(n + 1):
			arr.append(-1)
		return fun(n)


from functools import lru_cache

@lru_cache(maxsize=None)
def count_ways(n):
	if n == 0 or n == 1:
		return 1
	else:
		return count_ways(n - 1) + count_ways(n - 2)

class Solution:

	def countWays(self, n):
		return count_ways(n) % (10 ** 9 + 7)


class Solution:

	def countWays(self, n):
		if n == 1 or n == 2:
			return 1 if n == 1 else 2
		mod = 10 ** 9 + 7
		ans = [0 for _ in range(n)]
		ans[0] = 1
		ans[1] = 2
		for i in range(2, n):
			ans[i] = ans[i - 1] + ans[i - 2]
		return ans[n - 1] % mod


class Solution:

	def __init__(self):
		self.h = {}

	def countWays(self, n):
		if n == 0:
			return 1
		if n < 0:
			return 0
		elif self.h.get(n, -1) != -1:
			return self.h[n]
		self.h[n] = self.countWays(n - 1) + self.countWays(n - 2)
		return self.h[n] % 1000000007


import math

class Solution:

	def countWays(self, n, memo={}):
		mod = 10 ** 9 + 7
		if n in memo:
			return memo[n] % mod
		elif n == 0 or n == 1:
			return 1
		elif n == 2:
			return 2
		else:
			memo[n] = self.countWays(n - 1, memo) % mod + self.countWays(n - 2, memo) % mod
			return memo[n] % mod