Given a value N. In how many ways you can construct a grid of size N x 4 using tiles of size 1 x 4.
Example 1:
Input: N = 1
Output: 1
Explaination: We can arrange the tiles horizontally 
and this is the only way.
Example 2:
Input: N = 4
Output: 2
Explaination: The first way can be when all 
the 1 x 4 tiles are arranged horizontally. 
Second way can be when all the 1 x 4 tiles 
are arranged vertically.
Your Task:
You do not need to read input or print anything. Your task is to complete the function arrangeTiles() which takes the value N as input parameter and returns the number of ways to make N x 4 grid using 1 x 4 tiles.
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(N)
Constraints:
1 ≤ N ≤ 80

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 arrangeTiles(self, N):

        # code here

Solutions:
class Solution:

	def arrangeTiles(self, N):
		dp = [1] * (N + 1)
		for i in range(4, N + 1):
			dp[i] = dp[i - 1] + dp[i - 4]
		return dp[N]


class Solution:

	def arrangeTiles(self, N):
		n = N
		dp = [0] * (n + 1)
		dp[0] = 1
		dp[1] = 1
		m = 4
		for i in range(2, n + 1):
			dp[i] += dp[i - 1]
			if i - m >= 0:
				dp[i] += dp[i - m]
			dp[i] = dp[i]
		return dp[n]


class Solution:

	def arrangeTiles(self, n):
		if n == 1 or n == 2 or n == 3:
			return 1
		if n == 4:
			return 2
		dp = [-1 for i in range(n + 1)]
		dp[1] = 1
		dp[2] = 1
		dp[3] = 1
		dp[4] = 2
		for i in range(5, n + 1):
			dp[i] = dp[i - 1] + dp[i - 4]
		return dp[n]


class Solution:

	def arrangeTiles(self, N):
		dp = [0] * (N + 1)
		dp[0] = 1
		for i in range(1, N + 1):
			if i - 4 >= 0:
				dp[i] = dp[i - 1] + dp[i - 4]
			else:
				dp[i] = dp[i - 1]
		return dp[N]


from collections import defaultdict

class Solution:

	def arrangeTiles(self, N):
		d = defaultdict(lambda : 0)
		d[0] = 1
		for i in range(1, N + 1):
			d[i] = d[i - 1] + d[i - 4]
		return d[N]


class Solution:

	def arrangeTiles(self, N):
		dp = [-1] * (N + 1)
		if N <= 3:
			return 1
		dp[0] = 1
		dp[1] = 1
		dp[2] = 1
		dp[3] = 1
		dp[4] = 2
		for i in range(5, N + 1):
			dp[i] = dp[i - 1] + dp[i - 4]
		return dp[N]


from functools import lru_cache

class Solution:

	@lru_cache(maxsize=124)
	def arrangeTiles(self, N):
		if N < 4:
			return 1
		if N == 4:
			return 2
		ans = 0
		for i in range(5, N + 1):
			ans = self.arrangeTiles(N - 1) + self.arrangeTiles(N - 4)
		return ans


class Solution:

	def arrangeTiles(self, N):
		if N < 4:
			return 1
		elif N == 4:
			return 2
		else:
			res = [0] * (N + 1)
			res[0] = 0
			res[1] = 1
			res[2] = 1
			res[3] = 1
			res[4] = 2
			j = 1
			for i in range(5, N + 1):
				res[i] = res[i - 1] + res[j]
				j += 1
			return res[N]


class Solution:

	def arrangeTiles(self, N):
		if N <= 3:
			return 1
		dp_array = [0] * (N + 1)
		for i in range(N + 1):
			if i <= 3:
				dp_array[i] = 1
			else:
				dp_array[i] = dp_array[i - 1] + dp_array[i - 4]
		return dp_array[-1]


class Solution:

	def arrangeTiles(self, N):
		if N <= 3:
			return 1
		if N == 4:
			return 2
		a = 1
		b = 1
		c = 1
		d = 2
		for i in range(5, N + 1):
			e = a + d
			a = b
			b = c
			c = d
			d = e
		return d


facts = {}

def factorial(n):
	if n in facts:
		return facts[n]
	if n <= 1:
		return 1
	r = n * factorial(n - 1)
	facts[n] = r
	return r

def nCr(n, r):
	return factorial(n) // (factorial(n - r) * factorial(r))

class Solution:

	def arrangeTiles(self, N):
		t = 0
		for i in range(N // 4 + 1):
			a = N - 4 * i
			t += nCr(a + i, i)
		return t


class Solution:

	def arrangeTiles(self, N):
		grid = [0 for i in range(N + 1)]
		for i in range(1, N + 1):
			if i < 3:
				grid[i] = 1
			elif i == 4:
				grid[i] = 2
			else:
				grid[i] = grid[i - 1] + grid[i - 4]
		return grid[N]


class Solution:

	def arrangeTiles(self, N):
		data = [None] * (N + 1)
		if N == 1 or N == 2 or N == 3:
			return 1
		if N == 4:
			return 2
		data[1] = 1
		data[2] = 1
		data[3] = 1
		data[4] = 2
		for i in range(5, N + 1):
			data[i] = data[i - 1] + data[i - 4]
		return data[N]


class Solution:

	def f(self, ind, dp):
		if ind < 4:
			return 1
		if dp[ind] != -1:
			return dp[ind]
		dp[4] = 2
		dp[ind] = self.f(ind - 1, dp) + self.f(ind - 4, dp)
		return dp[ind]

	def arrangeTiles(self, N):
		dp = [-1] * (N + 1)
		return self.f(N, dp)


class Solution:

	def f(self, ind, dp):
		if ind < 4:
			return 1
		if dp[ind] != -1:
			return dp[ind]
		for i in range(1, 4):
			dp[ind] = 1
		dp[4] = 2
		dp[ind] = self.f(ind - 1, dp) + self.f(ind - 4, dp)
		return dp[ind]

	def arrangeTiles(self, N):
		dp = [-1] * (N + 1)
		return self.f(N, dp)


class Solution:

	def arrangeTiles(self, N):
		(a, b, c, d) = (1, 1, 1, 1)
		for i in range(N):
			(a, b, c, d) = (b, c, d, a + d)
		return a
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		N = int(input())
		ob = Solution()
		print(ob.arrangeTiles(N))


import sys

class Solution:

	def f(self, n):
		if n <= 3:
			return 1
		if n in self.tb:
			return self.tb[n]
		self.tb[n] = self.f(n - 1) + self.f(n - 4)
		return self.tb[n]

	def arrangeTiles(self, N):
		sys.setrecursionlimit(10 ** 6)
		self.tb = {}
		return self.f(N)
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		N = int(input())
		ob = Solution()
		print(ob.arrangeTiles(N))


class Solution:

	def arrangeTiles(self, N):

		def check(i):
			if i < 4:
				return 1
			if dp[i] != -1:
				return dp[i]
			dp[i] = check(i - 1) + check(i - 4)
			return dp[i]
		dp = [-1 for i in range(N + 1)]
		return check(N)
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		N = int(input())
		ob = Solution()
		print(ob.arrangeTiles(N))


class Solution:

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

	def recur(self, n, m):
		if (n, m) in self.cache:
			return self.cache[n, m]
		if n <= 3 or m <= 3:
			return 1
		else:
			self.cache[n, m] = self.recur(n - 1, m) + self.recur(n - 4, m)
			return self.cache[n, m]

	def arrangeTiles(self, N):
		if N == 0:
			return 0
		return self.recur(N, 4)
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		N = int(input())
		ob = Solution()
		print(ob.arrangeTiles(N))


class Solution:

	def arrangeTiles(self, N):

		def fun(i):
			if i == 0:
				return 1
			if i < 0:
				return 0
			if dp[i] != -1:
				return dp[i]
			count = 0
			count += fun(i - 1)
			count += fun(i - 4)
			dp[i] = count
			return dp[i]
		dp = [-1] * (N + 1)
		return fun(N)


class Solution:

	def arrangeTiles(self, N):
		t = [1] * (N + 1)
		for i in range(len(t)):
			if i < 4:
				t[i] = 1
			else:
				t[i] = t[i - 1] + t[i - 4]
		return t[N]


class Solution:

	def arrangeTiles(self, N):
		if N == 4:
			return 2
		if N < 4:
			return 1
		dp = [0] * (N + 1)
		dp[1] = 1
		dp[2] = 1
		dp[3] = 1
		dp[4] = 2
		i = 5
		while i <= N:
			dp[i] = dp[i - 1] + dp[i - 4]
			i += 1
		return dp[N]


class Solution:

	def arrangeTiles(self, N):
		if N <= 3:
			return 1
		temp = []
		for i in range(0, N + 1):
			temp.append(0)
		temp[0] = temp[1] = temp[2] = temp[3] = 1
		for i in range(4, N + 1):
			temp[i] = temp[i - 4] + temp[i - 1]
		return temp[i]


class Solution:

	def arrangeTiles(self, n):
		dp = [0] * (n + 1)
		for i in range(n + 1):
			if i <= 3:
				dp[i] = 1
			else:
				dp[i] = dp[i - 1] + dp[i - 4]
		return dp[-1]


class Solution:

	def arrangeTiles(self, N):
		f = []
		for i in range(0, N + 1):
			f.append(1)
		if N >= 4:
			f[4] = 2
		for i in range(5, N + 1):
			a = f[i - 1] + f[i - 4]
			f[i] = a
		res = f[-1]
		return res


import math

class Solution:

	def arrangeTiles(self, N):
		cnt = 1
		if N < 4:
			return 1
		else:
			for i in range(1, N // 4 + 1, 1):
				k = N - i * 4
				r = math.factorial(k + i) / (math.factorial(k) * math.factorial(i))
				cnt = cnt + r
			return int(cnt)


class Solution:

	def arrangeTiles(self, N):
		M = N + 5
		arr = [0] * M
		arr[0] = 1
		arr[1] = 1
		arr[2] = 1
		arr[3] = 1
		for i in range(4, N + 1):
			arr[i] = arr[i - 4] + arr[i - 1]
		return arr[N]


class Solution:

	def arrangeTiles(self, N):
		data = [0 for i in range(max(5, N + 1))]
		(data[1], data[2], data[3]) = (1, 1, 1)
		data[4] = 2
		for i in range(5, N + 1):
			data[i] = data[i - 1] + data[i - 4]
		return data[N]


class Solution:

	def arrangeTiles(self, N):
		if N < 4:
			return 1
		elif N == 4:
			return 2
		nums = []
		for x in range(0, N):
			if x < 4:
				nums.append(1)
			elif x == 4:
				nums.append(2)
			elif x > 4:
				nums.append(nums[x - 1] + nums[x - 4])
		return nums[N - 1] + nums[N - 4]


class Solution:

	def arrangeTiles(self, N):
		groups = N // 4
		remaining = N % 4
		self.combinations = 0
		result = 0
		for _ in range(groups + 1):
			top_fact = remaining + groups
			bottom_fact1 = groups
			bottom_fact2 = top_fact - bottom_fact1
			top_fact = self.calculate_factorial(top_fact, max(bottom_fact1, bottom_fact2))
			bottom_fact = self.calculate_factorial(min(bottom_fact1, bottom_fact2))
			result += int(top_fact / bottom_fact)
			groups -= 1
			remaining += 4
		return result

	def calculate_factorial(self, start, end=1):
		if start == end or start == 0:
			return 1
		return start * self.calculate_factorial(start - 1, end)


class Solution:

	def arrangeTiles(self, N):

		def f(N, memo):
			key = N
			if key in memo:
				return memo[key]
			if N <= 0:
				return 0
			if N < 4:
				return 1
			if N == 4:
				return 2
			memo[key] = f(N - 1, memo) + f(N - 4, memo)
			return f(N - 1, memo) + f(N - 4, memo)
		return f(N, memo={})


class Solution:

	def arrangeTiles(self, N):

		def NoWays(N, memo):
			if N in memo:
				return memo[N]
			if N < 4:
				return 1
			else:
				memo[N] = NoWays(N - 1, memo) + NoWays(N - 4, memo)
			return memo[N]
		return NoWays(N, memo={})


class Solution:

	def arrangeTiles(self, N):
		data = [None] * (N + 1)
		for i in range(1, N + 1):
			if i <= 3:
				data[i] = 1
			elif i == 4:
				data[i] = 2
			else:
				data[i] = data[i - 1] + data[i - 4]
		return data[N]


class Solution:

	def arrangeTiles(self, N):
		t = [-1] * (N + 1)

		def count(n):
			if t[n] != -1:
				return t[n]
			elif n == 0:
				t[n] = 0
				return 0
			elif n <= 3:
				t[n] = 1
				return 1
			elif n == 4:
				t[n] = 2
				return 2
			else:
				t[n] = count(n - 1) + count(n - 4)
				return t[n]
		return count(N)


class Solution:

	def arrangeTiles(self, N):
		dp = {1: 1, 2: 1, 3: 1, 4: 2}
		for num in range(5, N + 1):
			dp[num] = dp[num - 1] + dp[num - 4]
		return dp[N]