27626: AVL树最多有几层

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

n个结点的AVL树最多有多少层？

输入

整数n 。 0< n < 50,000,000

输出

AVL树最多有多少层

样例输入

20

样例输出

6

来源

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

from functools import lru_cache

@lru_cache(maxsize=None)
def min_nodes(h):
    if h == 0: return 0
    if h == 1: return 1
    return min_nodes(h-1) + min_nodes(h-2) + 1

def max_height(n):
    h = 0
    while min_nodes(h) <= n:
        h += 1
    return h - 1

n = int(input())
print(max_height(n))