백준 #1890 - 점프

 

action = {right, down} 대신 밟은 번호만큼 움직인다.

각 번호를 밟았을때 right, down 모두 해서 마지막 goal에 닿으면 된다.

goal에 닿으면 1을 return 한다.

이 값들을 누적하면 최종적으로 start에서 goal로 갈 수 있는 경로의 수를 알 수 있다.

N = int(input())
board = [list(map(int, input().split(' '))) for _ in range(N)]
memo = [[0 for _ in range(N)]for _ in range(N)]

def dp(board, memo, i, j):
    if i>=N or j>=N:
        return 0
    if i<N-1 and j<N-1 and board[i][j] == 0:
        return 0
    if memo[i][j] != 0:
        return memo[i][j]

    if i==j==N-1 and board[i][j] == 0:
        return 1
    a = dp(board,memo, i, j+board[i][j])
    d = dp(board,memo, i+board[i][j], j)
    
    memo[i][j] = a+d
    return memo[i][j]

res = dp(board,memo, 0, 0)
print(res)