[Algorithms] 동적 계획법(Dynamic Programming)-알리바바와 40인의 도둑(Bottom-Up & Top-Down)

 

 

 

 

 

• 작은 부분부터 보면서 규칙을 파악해 본다 
• 계산식이 2가지 부분으로 나뉘는데 1번째는 맨 위 라인과 맨 왼쪽 라인에 대해 Bottom up 동적계획법으로 값을 구한다는 것 + 2번째는 나머지 부분에 대해 왼쪽과 위쪽 중에 다이나믹 배열 상에서 더 작은 값을 선택해서 Bottom up 동적계획법으로 풀어나간다는 것 

    n = int(input())
    board = [list(map(int, input().split())) for _ in range(n)]
 
    for i in range(1, n):
        board[0][i] += board[0][i-1]
        board[i][0] += board[i-1][0]
 
    for i in range(1, n):
        for j in range(1, n):
            if board[i-1][j] > board[i][j-1]:
                board[i][j] = board[i][j] + board[i][j-1]
            else:
                board[i][j] = board[i][j] + board[i-1][j]
 
    print(board[n-1][n-1])

 

 

 

 

 

 

 

 

 

 

• 이제 Top-Down으로 풀어보자 

def DFS(x, y):
 
    if memo[x][y] != 0:          # memoization 으로 cut edge를 해준다
        return memo[x][y]
 
    if x==y==0:
        return board[0][0]
    else:
        if y==0:
            memo[x][0] = DFS(x-1, 0) + board[x][0]
        elif x==0:
            memo[0][y] = DFS(0, y-1) + board[0][y]
        else:
            memo[x][y] = min(DFS(x-1, y), DFS(x, y-1)) + board[x][y]    # 더 작은 값에다가 현재의 값을 더해준다
        return memo[x][y]
 
if __name__=='__main__':
 
    n = int(input())
    board = [list(map(int, input().split())) for _ in range(n)]
    memo = [[0]*n for _ in range(n)]
 
    print(DFS(n-1, n-1))