dp.py

;compile python
```
import functools
@functools.lru_cache(None)
def solve(n):
  if n <= 1:
    return 0
  if n == 2:
    return (1/3) ** 2
  return (1/3) * ((1/3) + (2/3) * solve(n - 2)) + (2/3) * solve(n - 1)

for i in range(11):
  print(f"{i}: {solve(i)}")
```