There are N stairs, and 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 not matter).
Note: Order does not matter means for n=4 {1 2 1},{2 1 1},{1 1 2} are considered same.
Example 1:
Input:
N = 4
Output: 3
Explanation: You can reach 4th stair in
3 ways.
3 possible ways are:
1, 1, 1, 1
1, 1, 2
2, 2
Example 2:
Input:
N = 5
Output: 3
Explanation:
You may reach the 5th stair in 3 ways.
The 3 possible ways are:
1, 1, 1, 1, 1
1, 1, 1, 2
1, 2, 2
Your Task:
Your task is to complete the function countWays() which takes single argument(N) and returns the answer.
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(N)
Constraints:
1 <= N <= 10^{6}

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Dynamic programming

Mathematics

Starter code: #User function Template for python3

class Solution:
    
    #Function to count number of ways to reach the nth stair 
    #when order does not matter.
    def countWays(self,m):
        
        mod = 1000000007
        # code here

Solutions:
class Solution:

	def countWays(self, m):
		mod = 1000000007
		ans = 1
		while m - 1 > 0:
			ans = (ans + 1) % mod
			m = m - 2
		return ans


class Solution:

	def countWays(self, m):
		mod = 1000000007
		return int(m / 2 + 1)


class Solution:

	def nthStair1(self, a, n, W):
		global dp
		if W == 0:
			return 1
		if n == 0:
			return 0
		if dp[n][W] != -1:
			return dp[n][W]
		if a[n - 1] <= W:
			dp[n][W] = self.nthStair1(a, n, W - a[n - 1]) + self.nthStair1(a, n - 1, W)
			return dp[n][W]
		else:
			dp[n][W] = self.nthStair1(a, n - 1, W)
			return dp[n][W]

	def countWays(self, m):
		mod = 1000000007
		global dp
		dp = [[-1 for i in range(m + 1)] for j in range(2 + 1)]
		a = [1, 2]
		return self.nthStair1(a, 2, m)


class Solution:

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


class Solution:

	def countWays(self, m):
		return (m // 2 + 1) % 1000000007


class Solution:

	def countWaysHelper(self, m, arr, n, memo):
		mod = 1000000007
		if (m, n) in memo:
			return memo[m, n]
		if m == 0:
			return 1
		if n == 0 or m < 0:
			return 0
		ans1 = self.countWaysHelper(m - arr[n - 1], arr, n, memo)
		ans2 = self.countWaysHelper(m, arr, n - 1, memo)
		memo[m, n] = (ans1 + ans2) % mod
		return memo[m, n]

	def countWays(self, m):
		return self.countWaysHelper(m, [1, 2], 2, dict())


class Solution:

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


class Solution:

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


class Solution:

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


class Solution:

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


class Solution:

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

		def recursive(dp, arr, n, m):
			if m == 0:
				return 1
			if n == 0:
				return 0
			if dp[m][n] != -1:
				return dp[m][n]
			dp[m][n] = recursive(dp, arr, n - 1, m)
			if m - arr[n - 1] >= 0:
				dp[m][n] += recursive(dp, arr, n, m - arr[n - 1])
			return dp[m][n]
		return recursive(dp, arr, n, m)


class Solution:

	def countWays(self, m):
		n = m
		dp = [0] * (n + 1)
		dp[0] = 1
		for i in range(1, n + 1):
			os = dp[i - 1]
			ts = 0
			if i > 1:
				ts = dp[i - 2]
			dp[i] = int((os + ts) / 2) + 1
		return dp[n]


class Solution:

	def countWays(self, m):
		mod = 1000000007
		dp = [0 for _ in range(m + 1)]
		dp[0] = 1
		for i in range(1, 3):
			for j in range(i, m + 1):
				dp[j] += dp[j - i]
		return dp[m]


class Solution:

	def countWays(self, m):
		count = 0
		for x in range(m + 1):
			if (m - x) % 2 == 0:
				count += 1
		return count


class Solution:

	def count(self, m):
		if m == 1:
			return 1
		if m <= 0:
			return 0
		ans = self.count(m - 1) + self.count(m - 2)
		return ans

	def countWays(self, m):
		mod = 1000000007
		dp = [0 for _ in range(m + 1)]
		dp[0] = 1
		dp[1] = 1
		for i in range(2, m + 1):
			dp[i] = 1 + min(dp[i - 1], dp[i - 2])
		return dp[m]


class Solution:

	def countWays(self, n):
		mod = 1000000007
		if n == 1:
			return 1
		if n == 2:
			return 2
		p1 = 1
		p2 = 2
		for i in range(3, n + 1):
			c = (min(p1, p2) + 1) % mod
			p1 = p2
			p2 = c
		return c


class Solution:
	mod = 1000000007

	def util(self, n):
		if n == 1:
			return 1
		if n == 2 or n == 3:
			return 2
		return 1 + max(self.util(n - 1), self.util(n - 2)) % self.mod

	def countWays(self, m):
		return m // 2 + 1


class Solution:

	def countWays(self, m):
		from math import floor as fl
		return fl(m / 2 + 1)


class Solution:

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


class Solution:

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


class Solution:

	def countWays(self, m):
		return m // 2 + 1
		mod = 1000000007
		if m == 0:
			return 1
		res = 1
		for i in range(1, m + 1):
			if i % 2 == 0:
				res += 1
		return res


class Solution:

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

		def count(n, dp):
			if n <= 2:
				return n
			if n < 0:
				return 0
			if dp[n] == -1:
				dp[n] = 1 + count(n - 2, dp)
			return dp[n] % mod
		return count(m, dp)


class Solution:

	def countWays(self, m):
		if m == 2:
			return 2
		if m == 1:
			return 1
		res = 0
		while m >= 2:
			m = m - 2
			res += 1
		return res + 1


class Solution:

	def countWays(self, n):
		mod = 1000000007
		result = self.solve(n)
		return result % mod

	def solve(self, n):
		minus1 = minus2 = 0
		for i in range(n + 1):
			result = 1 + min(minus1, minus2)
			minus2 = minus1
			minus1 = result
		return result


class Solution:

	def countWays(self, n):
		mod = 1000000007
		result = self.solve(n)
		return result % mod

	def solve(self, n):
		times = max(2, n + 1)
		dp = [0 for i in range(times)]
		dp[0] = dp[1] = 1
		for i in range(2, n + 1):
			dp[i] = 1 + min(dp[i - 1], dp[i - 2])
		return dp[n]


class Solution:

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

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


class Solution:

	def countWays(self, n):
		mod = 1000000007
		result = 1 + n // 2
		return result % mod


class Solution:

	def countWays(self, m):
		mod = 1000000007
		if m < 2:
			return 1
		return (m // 2 + 1) % mod


class Solution:

	def countWays(self, m):
		if m <= 2:
			return m
		return m // 2 + 1


class Solution:

	def countWays(self, m):
		global mod
		mod = 1000000007

		def recurs(m):
			if m == 0:
				return 1
			if m < 0:
				return 0
			p = recurs(m - 2)
			q = recurs(m - 1)
			return (p % mod + q % mod) % mod
		return int(m / 2) + 1


class Solution:

	def countWays(self, m):
		t = [-1 for i in range(m + 1)]
		return self.helper(m, t)

	def helper(self, m, t):
		if m == 0:
			return 1
		if m < 0:
			return 0
		if t[m] != -1:
			return t[m]
		step1 = self.helper(m - 1, t)
		step2 = self.helper(m - 2, t)
		t[m] = 1 + min(step1, step2)
		return t[m]


class Solution:

	def countWays(self, m):
		mod = 1000000007
		d = {0: 1, 1: 1, 2: 2}
		for i in range(2, m + 1):
			d[i] = min(d[i - 1] % mod, d[i - 2] % mod) + 1
		return d[m] % mod


class Solution:

	def countWays(self, m):
		mod = 1000000007
		possible = [1, 2]
		no_of_ele = 2
		dp = [0] * (m + 1)
		dp[0] = 1
		for i in range(no_of_ele):
			for j in range(m + 1):
				if j - possible[i] >= 0:
					dp[j] = dp[j] + dp[j - possible[i]]
		return dp[m] % mod


MOD = pow(10, 9) + 7

class Solution:

	def countWays(self, m):
		return 1 + m // 2


class Solution:

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


class Solution:

	def __init__(self):
		self.d = {}
		self.res = set()

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


class Solution:

	def countWays(self, m):
		dp = [-1 for i in range(m + 1)]
		dp[0] = 0
		dp[1] = 1
		if m > 1:
			for i in range(2, m + 1):
				if i == 2:
					way1 = dp[i - 1]
					way2 = 100000
				else:
					way1 = dp[i - 1]
					way2 = dp[i - 2]
				dp[i] = min(way1, way2) + 1
		return dp[m]


class Solution:

	def countWays(self, m):
		dp = [-1 for i in range(m + 1)]
		dp[0] = 0
		dp[1] = 1
		if m > 1:
			dp[2] = 2
			for i in range(3, m + 1):
				way1 = dp[i - 1]
				way2 = dp[i - 2]
				dp[i] = min(way1, way2) + 1
		return dp[m]
		mod = 1000000007


class Solution:

	def countWays(self, m):
		mod = 1000000007
		count = 1
		while m > 1:
			m -= 2
			count += 1
		return count


class Solution:

	def countWays(self, m):
		mod = 1000000007
		dp = [[-1 for i in range(m + 1)] for j in range(m + 1)]
		dec = {}
		self.ans = 0

		def solve(st, no):
			if st == 0:
				if dec.get(no) == None:
					dec[no] = 1
					self.ans += 1
					return 0
				return 0
			if st < 0:
				return 0
			if dp[no][st] != -1:
				return dp[no][st]
			dp[no][st] = solve(st - 1, no + 1) + solve(st - 2, no + 1)
			return dp[no][st]
		solve(m, 0)
		return self.ans


class Solution:

	def countWays(self, m):
		mod = 1000000007
		dp = [[0 for i in range(2)] for j in range(m + 1)]
		for i in range(2):
			dp[0][i] = 1
		arr = [i + 1 for i in range(2)]
		for i in range(1, m + 1):
			for j in range(2):
				take = dp[i - arr[j]][j] if i >= arr[j] else 0
				nottake = dp[i][j - 1] if j > 0 else 0
				dp[i][j] = take + nottake
		return dp[m][1]


class Solution:

	def countWays(self, m):
		dt = [[-1 for i in range(m + 1)] for j in range(3)]

		def ab(m, d=[1, 2], n=2):
			if m == 0:
				return 1
			if n == 0 or m < 0:
				return 0
			if dt[n][m] != -1:
				return dt[n][m]
			a = ab(m, d[1:], n - 1)
			b = ab(m - d[0], d, n)
			dt[n][m] = a + b
			return a + b
		return ab(m)


class Solution:

	def countWays(self, m):

		def ab(m, d=[1, 2], n=2):
			if m == 0:
				return 1
			if n == 0 or m < 0:
				return 0
			a = ab(m, d[1:], n - 1)
			b = ab(m - d[0], d, n)
			return a + b
		return ab(m)


class Solution:

	def countWays(self, m):
		return m // 2 + 1
import atexit
import io
import sys
if __name__ == '__main__':
	test_cases = int(input())
	for cases in range(test_cases):
		m = int(input())
		ob = Solution()
		print(ob.countWays(m))


class Solution:

	def countWays(self, n):
		a = [1, 2]
		m = len(a)

		def check(i, j):
			if j == 0:
				return 1
			if i == 0:
				return 1
			take = 0
			if a[i] <= j:
				take = check(i, j - a[i])
			nottake = check(i - 1, j)
			return take + nottake
		m1 = check(m - 1, n)
		return m1
import atexit
import io
import sys
if __name__ == '__main__':
	test_cases = int(input())
	for cases in range(test_cases):
		m = int(input())
		ob = Solution()
		print(ob.countWays(m))


class Solution:

	def countWays(self, m):
		modulo = 10 ** 9 + 7
		if m == 0:
			return 1
		elif m == 1 or m == 2:
			return m
		dp = [0] * (m + 1)
		dp[0] = 1
		dp[1] = 1
		dp[2] = 2
		for i in range(3, m + 1):
			dp[i] = (dp[i - 2] + 1) % modulo
		return dp[m]
import atexit
import io
import sys
if __name__ == '__main__':
	test_cases = int(input())
	for cases in range(test_cases):
		m = int(input())
		ob = Solution()
		print(ob.countWays(m))


class Solution:

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

	def countWays(self, n):
		if n == 1 or n == 2:
			return n
		if n in self.d:
			return self.d[n]
		a1 = self.countWays(n - 1)
		a2 = self.countWays(n - 2)
		self.d[n] = min(a1, a2) + 1
		return self.d[n]


class Solution:

	def countWays(self, m):
		mod = 1000000007
		arr = [0] * (m + 2)
		arr[0] = 0
		arr[1] = 1
		for i in range(2, m + 2):
			arr[i] = arr[i - 2] + 1
		return arr[m + 1] % (10 ** 9 + 7)
import atexit
import io
import sys
if __name__ == '__main__':
	test_cases = int(input())
	for cases in range(test_cases):
		m = int(input())
		ob = Solution()
		print(ob.countWays(m))


class Solution:

	def countWays(self, m):
		if m < 3:
			return m
		dp = [0] * (m + 1)
		dp[0] = 0
		dp[1] = 1
		dp[2] = 2
		for i in range(3, m + 1):
			dp[i] = min(dp[i - 1], dp[i - 2]) + 1
		return dp[m]
import atexit
import io
import sys
if __name__ == '__main__':
	test_cases = int(input())
	for cases in range(test_cases):
		m = int(input())
		ob = Solution()
		print(ob.countWays(m))