The Padovan sequence is the sequence of integers `P(n)` defined by the initial values

`P(0)=P(1)=P(2)=1`

and the recurrence relation

`P(n)=P(n-2)+P(n-3)`

The first few values of `P(n)` are

`1, 1, 1, 2, 2, 3, 4, 5, 7, 9, 12, 16, 21, 28, 37, 49, 65, 86, 114, 151, 200, 265, ...`

### Task 

The task is to write a method that returns i-th Padovan number

```python
> padovan(0) == 1
> padovan(1) == 1
> padovan(2) == 1
> padovan(n) = padovan(n-2) + padovan(n-3)
```

Difficulty: introductory

Starter code:

def padovan(n):
	

Solutions:
def padovan(n):
    p0 = p1 = p2 = 1
    for i in range(n):
        p0, p1, p2 = p1, p2, p0 + p1
    return p0

from functools import lru_cache

@lru_cache(maxsize=None)
def padovan(n):
    return n<3 or padovan(n-2) + padovan(n-3)

from functools import lru_cache

@lru_cache()
def padovan(n):
    return 1 if n < 3 else padovan(n-2) + padovan(n-3)

def padovan(n):
  p0 = p1 = p2 = 1
  for i in range(3, n+1):
    p0, p1, p2 = p1, p2, p0+p1
  return p2

from collections import deque

def padovan(n):
    q = deque([1,1,1], maxlen=3)
    for i in range(n-2):
        q.append(q[0] + q[1])
    return q[-1]

def padovan(n):
    a = b = c = 1
    while n:
        a, b, c = b, c, a + b
        n -= 1
    return a

def padovan(n, a=1, b=1, c=1):
    return a if n==0 else padovan(n-1, b, c, a+b)

def padovan(n):
    a = b = c = 1
    for i in range(n // 3):
        a += b
        b += c
        c += a
    return (a, b, c)[n % 3]

import sys
sys.setrecursionlimit(1500) 

def padovan(n, memo = {0:1, 1:1, 2:1}):
    if n in memo: return memo[n]
    else:
        result = padovan(n-2,memo) + padovan(n-3, memo)
        memo[n] = result
        return result

def memoize(f):
    memo = {}
    def helper(x):
        if x not in memo:            
            memo[x] = f(x)
        return memo[x]
    return helper

def padovan(n):
    if n==0 or n==1 or n==2:
        return 1
    else:
        return padovan(n-2)+padovan(n-3)
        
padovan=memoize(padovan)