[python][algospot] 외발뛰기 (JUMPGAME)

[구종만의 알고리즘 문제해결전략] 내용을 파이썬으로 변경

n = 7
board = [[2,5,1,6,1,4,1],
         [6,1,1,2,2,9,3],
         [7,2,3,2,1,3,1],
         [1,1,3,1,7,1,2],
         [4,1,2,3,4,1,2],  # [4,1,2,3,4,1,3], [4,1,2,3,4,1,2]
         [3,3,1,2,3,4,1],
         [1,5,2,9,4,7,0]]

def jump(x,y):
    if x >= n or y >= n: return  False  # 게임판 밖을 벗어남.
    if x == n-1 and y == n-1:
        # print(board[x][y], x, y)
        return True  # 마지막칸에 도착한경우.
    jump_size = board[x][y]
    
    return jump(x+jump_size, y) or jump(x, y+jump_size)

print(jump(0,0))


# 동적 계획법
cache = [ [None]*n for _ in range(n)]
# print('cache', cache)
def jump2(x,y):
    if x >= n or y >= n: return False
    if x == n-1 and y == n-1: return True

    if cache[x][y] is not None:
        return cache[x][y]
    else:
        jump_size = board[x][y]
        cache[x][y] = jump2(x+jump_size, y) or jump2(x, y+jump_size)
        return cache[x][y]
print(jump2(0,0))