sum_fibonacci(35)

fibcache = {}
def  sum_fibonacci(n):
    if n == 0:
        fibcache[n] = 0
        return fibcache[n]
    elif n == 1:
        fibcache[n] = 1
        return fibcache[n]
    else:
        sum_left = 0
        sum_right = 0
        if n-2 in fibcache.keys():
            sum_left += fibcache[n-2]
        else:
            sum_left += sum_fibonacci(n-2)
            fibcache[n-2] = sum_left
        if n-1 in fibcache.keys():
            sum_right += fibcache[n-1]
        else:
            sum_right += sum_fibonacci(n-1)
            fibcache[n-1] = sum_right
        return sum_left + sum_right