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: Three ways to reach at 4th stair.
They are {1, 1, 1, 1}, {1, 1, 2}, {2, 2}.
Example 2:
Input: N = 5
Output: 3
Explanation: Three ways to reach at 5th stair.
They are {1, 1, 1, 1, 1}, {1, 1, 2, 1} and
{1, 2, 2}.
Your Task:
You don't need to read or print anyhting. Your task is to complete the function nthStair() which takes N as input parameter and returns the total number of ways to reach at Nth stair.
 
Expected Time Complexity: O(N)
Expected Space Complexity: O(N)
 
Constraints:
1 ≤ N ≤ 10^{4}

Difficulty: MEDIUM
Tags: Dynamic programming

Mathematics
Skill types: Dynamic programming
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(N)

Starter code:
#User function Template for python3



class Solution:

	def nthStair(self,n):

		# Code here

Solutions:
class Solution:

	def nthStair(self, n):
		if n <= 0:
			return 0
		if n == 1:
			return 1
		if n == 2:
			return 2
		a = self.nthStair(n - 2) + 1
		return a


class Solution:

	def nthStair(self, n):
		return int(n / 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 nthStair(self, n):
		global dp
		dp = [[-1 for i in range(n + 1)] for j in range(2 + 1)]
		a = [1, 2]
		return self.nthStair1(a, 2, n)


class Solution:

	def nthStair(self, n):
		dp = [0] * (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 nthStair(self, n):
		if n % 2 == 1:
			q = n // 2
			r = n % 2
			a = q + r
			return a
		else:
			q = n // 2
			r = n % 2
			a = q + r
			return a + 1


class Solution:

	def nthStair(self, n):
		if n == 1:
			return 1
		elif n == 2:
			return 2
		else:
			return self.nthStair(n - 2) + 1


class Solution:

	def nthStair(self, n):
		if n % 2 == 0:
			return n // 2 + 1
		else:
			return n // 2 + 1


class Solution:

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

		def recursive(dp, arr, n, idx=2):
			if n == 0:
				return 1
			if idx == 0:
				return 0
			if dp[n][idx] != -1:
				return dp[n][idx]
			dp[n][idx] = recursive(dp, arr, n, idx - 1)
			if arr[idx - 1] <= n:
				dp[n][idx] += recursive(dp, arr, n - arr[idx - 1], idx)
			return dp[n][idx]
		return recursive(dp, arr, n)


class Solution:

	def nthStair(self, n):
		ans = n // 2 + 1
		return ans


class Solution:

	def __init__(self):
		self.dic = {0: 1, 1: 1}

	def nthStair(self, n):
		return n // 2 + 1


class Solution:

	def nthStair(self, n):
		if n == 1:
			return 1
		return n // 2 + 1


class Solution:

	def nthStair(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]
		return sum(dp[n - 1])


class Solution:

	def countWays(self):
		cache = {}
		cache[0] = 1

		def count(n):
			if n == 0:
				return cache[n]
			elif n < 0:
				cache[n] = 0
				return cache[n]
			else:
				cache[n] = count(n - 2) + 1
				return cache[n]
		return count

	def nthStair(self, n):
		memoization = self.countWays()
		ans = memoization(n)
		return ans


class Solution:

	def countWays(self, n):
		if n == 0:
			return 1
		elif n < 0:
			return 0
		else:
			return self.countWays(n - 2) + 1

	def nthStair(self, n):
		ans = self.countWays(n)
		return ans


class Solution:

	def nthStair(self, n):
		count = 0
		for x in range(n + 1):
			count += (n - x) % 2 == 0
		return count


from collections import defaultdict

class Solution:
	arr = defaultdict(int)
	arr[0] = 1
	arr[1] = 1

	def nthStair(self, n):
		return n // 2 + 1


class Solution:

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

	def nthStair(self, n):
		if n <= 1:
			return n
		dp = [-1] * (n + 1)
		self.fib(n, dp)
		return dp[n]


class Solution:
	dp = []

	def util(self, n):
		if self.dp[n] != -1:
			return self.dp[n]
		if n == 0:
			return 1
		first = self.util(n - 1)
		second = 0
		if n > 1:
			second = self.util(n - 2) + 1
		self.dp[n] = max(first, second)
		return self.dp[n]

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


class Solution:

	def nthStair(self, n):
		dp = [1, 2]
		if n == 1:
			return 1
		if n == 2:
			return 2
		for i in range(2, n):
			dp.append(1 + dp[i - 2])
		return dp[n - 1]


class Solution:

	def nthStair(self, n):
		if n == 0:
			return 1
		if n in (1, 2):
			return n
		return n // 2 + 1


class Solution:

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


class Solution:
	cache = {}

	def nthStair(self, n):
		return self.fib(n + 1)

	def fib(self, number):
		if number in Solution.cache:
			return Solution.cache[number]
		if number < 2:
			respuesta = number
		else:
			respuesta = self.fib(1) + self.fib(number - 2)
		Solution.cache[number] = respuesta
		return Solution.cache[number]


class Solution:

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

		def solve(n, dp):
			if n == 0 or n == 1:
				return 1
			if dp[n] != -1:
				return dp[n]
			dp[n] = 1 + min(solve(n - 1, dp), solve(n - 2, dp))
			return dp[n]
		return solve(n, dp)


class Solution:

	def nthStair(self, n):
		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 nthStair(self, n):
		x = n // 2
		return n // 2 + 1


class Solution:

	def generate(self, n, path, ans):
		cur = path[-1][0]
		if cur == n:
			val = path[:]
			val.sort()
			if val not in ans:
				ans.append(val)
			return
		if cur > n:
			return
		path.append(cur + 1)
		self.generate(n, path, ans)
		path.pop()
		path.append(cur + 2)
		self.generate(n, path, ans)
		path.pop()

	def nthStair(self, n):
		return n // 2 + 1


class Solution:

	def nthStair(self, n):
		if n == 1:
			return 1
		if n == 2:
			return 2
		dp = [0] * (n + 1)
		dp[1] = 1
		dp[2] = 2
		for i in range(3, n + 1):
			dp[i] = min(dp[i - 1] + 1, dp[i - 2] + 1)
		ans = dp[n]
		return ans


class Solution:

	def nthStair(self, n):
		dp = []
		dp.append(1)
		dp.append(1)
		i = 2
		while i <= n:
			dp.append(dp[i - 2] + 1)
			i = i + 1
		return dp[n]


class Solution:

	def nthStair(self, n):
		a = 1
		for i in range(2, n + 1):
			if i % 2 == 0:
				a = a + 1
		return a


class Solution:

	def nthStair(self, n):
		if n <= 2:
			return n
		dic = {}
		dic[1] = 1
		dic[2] = 2
		for i in range(3, n + 1):
			if i % 2 == 0:
				dic[i] = dic[i - 1] + 1
			else:
				dic[i] = dic[i - 1]
		return dic[n]


class Solution:

	def nthStair(self, n):
		d = [0 for i in range(n + 1)]
		d[0] = 1
		d[1] = 1
		for j in range(2, n + 1):
			d[j] = d[j - 2] + 1
		return d[n]


class Solution:

	def nthStair(self, n):
		if n == 0:
			1
		res = [0 if i > 0 else 1 for i in range(n + 1)]
		for i in range(1, n + 1):
			if i % 2 == 0:
				res[i] = res[i - 1] + 1
			else:
				res[i] = res[i - 1]
		return res[n]


class Solution:

	def nthStair(self, n):
		dp = [-1] * (n + 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]
		return count(n, dp)


def stairDP(n, dp):
	if n == 0:
		return 1
	if n < 0:
		return 0
	if dp[n] != -1:
		return dp[n]
	dp[n] = stairDP(n - 2, dp) + 1
	return dp[n]

class Solution:

	def nthStair(self, num):
		dp = [1]
		for n in range(1, num + 1):
			local = 1
			if n - 2 >= 0:
				local = dp[n - 2] + 1
				dp.append(local)
			else:
				dp.append(local)
		return dp[-1]


def stairDP(n, dp):
	if n == 0:
		return 1
	if n < 0:
		return 0
	if dp[n] != -1:
		return dp[n]
	dp[n] = stairDP(n - 2, dp) + 1
	return dp[n]

class Solution:

	def nthStair(self, num):
		dp = [-1] * (num + 1)
		return stairDP(num, dp)


class Solution:

	def nthStair(self, n):
		x = 0
		y = 0
		a = 0
		ways = []
		while a <= n:
			y = a
			x = (n - y) / 2
			a = a + 1
			if x == int(x):
				z = (int(x), int(y))
				ways.append(z)
		return len(ways)