memo = {}
def rec(i, nums):
    if i >= len(nums):
        return 0
    if i in memo:
        return memo[i]
    # 配る
    ans = max(rec(i + 1, nums), rec(i + 2, nums) + nums[i])
    # 結果をメモ
    memo[i] = ans
    return ans

assert rec(0, [2,7,9,3,1]) == 12