27625: AVL树至少有几个结点

http://cs101.openjudge.cn/practice/27625/

输入n(0<n<50),输出一个n层的AVL树至少有多少个结点。

输入

n

输出

答案

样例输入

4

样例输出

7

来源

http://dsbpython.openjudge.cn/dspythonbook/P1350/

from functools import lru_cache

@lru_cache(maxsize=None)
def avl_min_nodes(n):
    if n == 0:
        return 0
    elif n == 1:
        return 1
    else:
        return avl_min_nodes(n-1) + avl_min_nodes(n-2) + 1

n = int(input())
min_nodes = avl_min_nodes(n)
print(min_nodes)