euler 502

gistfile1.py

store = {}

def g(w, h, odd=True):
    if w <= 0 or h <= 0:
        if odd: return 0
        return 1

    if not odd:
        return (h+1)**w - g(w, h)

    if (w, h) in store:
        return store[(w, h)]


    total = 0
    total = g(w-1, h)
    for i in range(w):
        total += g(i+1, h-1, False) * g(w-i-2, h, False)
        total += g(i+1, h-1, True) * g(w-i-2, h, True)

    store[(w,h)] = total
    return total

def F(w, h):
    v = g(w, h-1) - g(w, h-2)
    return v

assert F(4, 2) == 10
assert F(13, 10) == 3729050610636
assert F(10, 13) == 37959702514
assert F(100, 100) % 1000000007 == 841913936