We have two types of tiles: a 2x1 domino shape, and an "L" tromino shape. These shapes may be rotated.


XX  <- domino

XX  <- "L" tromino
X


Given N, how many ways are there to tile a 2 x N board? Return your answer modulo 10^9 + 7.

(In a tiling, every square must be covered by a tile. Two tilings are different if and only if there are two 4-directionally adjacent cells on the board such that exactly one of the tilings has both squares occupied by a tile.)



Example:
Input: 3
Output: 5
Explanation: 
The five different ways are listed below, different letters indicates different tiles:
XYZ XXZ XYY XXY XYY
XYZ YYZ XZZ XYY XXY

Note:


       N  will be in range [1, 1000].

Difficulty: interview

Starter code:

class Solution:
    def numTilings(self, N: int) -> int:
        

Solutions:
class Solution:
     def isIdealPermutation(self, A):
         """
         :type A: List[int]
         :rtype: bool
         """
         # tle
         # for i in range(len(A)-2):
             # if A[i] > min(A[i+2:]):
                 # return False
         # return True
                 
         # ac
         for i in range(len(A)):
             if abs(A[i] - i) > 1:
                 return False
         return True

'''
 # Brute Force
 class Solution:
     def isIdealPermutation(self, A):
         """
         :type A: List[int]
         :rtype: bool
         """
         countGlobal = 0
         countLocal = 0
         for i in range(len(A)):
             for j in range(i+1, len(A)):
                 if A[i] > A[j]:
                     countGlobal += 1
         
         for i in range(len(A)-1):
             if  A[i] > A[i+1]:
                 countLocal += 1
         
         if countLocal == countGlobal:
             return True
         else:
             return False
 '''     
 class Solution:
     def isIdealPermutation(self, A):
         for i in range(len(A)):
             if abs(A[i]-i) >= 2:
                 return False
         return True
         

class Solution:
     def isIdealPermutation(self, A):
         for i in range(len(A)):
             if abs(A[i] - i) > 1:
                 return False
         return True

class Solution:
     def isIdealPermutation(self, A):
         """
         :type A: List[int]
         :rtype: bool
         """
         
         l=[]
         [1,0,3,2]
         # ix=0
         # while ix<len(A)-1:
         #     if A[ix]>A[ix+1]:
         #         l.append(A[ix])
         #         ix+=2
         #         if A[ix]<l[-1]:return False
         #     else:
         #         ix+=1
         # return True
         if len(A)==1:return True
         for i in range(len(A)):
             if abs(A[i]-i)>1:return False
         return True

class Solution:
     def isIdealPermutation(self, A):
         """
         :type A: List[int]
         :rtype: bool
         """
         max_value = A[0]
         for i in range(1,len(A)-1):
             if A[i+1] < max_value:
                 return False
             if A[i] > max_value:
                 max_value = A[i]
         else:
             return True
         # local_count = 0
         # global_count = 0
         # for i in range(len(A)-1):
         #     if A[i] > A[i+1]:
         #         local_count += 1
         #     for j in range(len(A)):
         #         if A[i] > A[j] and i < j:
         #             global_count += 1
         # return local_count == global_count


class Solution:
     def isIdealPermutation(self, A):
         """
         :type A: List[int]
         :rtype: bool
         """
         return all(abs(v-i)<=1 for i,v in enumerate(A)) #有意思 其中的原理更有意思

class Solution:
     def isIdealPermutation(self, A):
         i = 0
         while i < len(A) - 1:
             if A[i] == i:
                 i += 1
             elif A[i] == i + 1 and A[i+1] == i:
                 i += 2
             else:
                 return False
         return True