1. DP 란

요즘 유행하는 드라마 DP아닙니다..!

1) 동적계획법

동적 계획법이란 큰 문제를 작은문제로 나누어 푸는 문제를 말한다. 동적 계획법이란 말 때문에 동적으로 프로그램이 진행 되는지는 몰라도 된다. 왜냐하면.. 동적프로그래밍이란 말을 창조한 사람이 그냥 멋있어서 이름을 부여했기 때문이다.

2) 사용 예시

어딘가의 목적지로 향하는데 있어 통과 해야 할 톨게이트가 있다고 가정해보자.
이때 어떠한 경로를 거쳐서 가야 비용이 가장 적게 부과가 되는지 찾는 방법을 찾아보자.

위의 문제를 해결 하기 위해 DP를 사용해야 하며, 비슷한 예제를 아래에서 확인해보자.

2. DP with 코드

위의 문제는
1 3 1
1 5 1
4 2 1
이렇게 되어있는 3*3에의 좌측 상단에서 시작하여 우하단까지 가는 최소비용을 구하는 문제이다.

이 문제를 풀기위해 나는 다음과 같은 코드를 작성 하였다.

def min_path_sum(grid):
 m_len = len(grid)
 n_len = len(grid[0])

 for m in range(1, m_len):
   grid[0][m] += grid[0][m-1]
   #row의 값을 초기화 시켜주는 과정이다

 for n in range(1, n_len):
   grid[n][0] += grid[n-1][0]
   #column의 값을 초기화 시켜주는 과정이다
   
   #위의 과정을 거치고 나면(x는 신경쓰지 말 것)
   #1 4 5
   #2 x x
   #6 x x
   #이렇게 완성이 된다.
   
   
 
 for m in range(1, m_len):
   for n in range(1, n_len):
     grid[n][m] += min(grid[n-1][m], grid[n][m-1])
 #위의 작업은 x로 오기 전의 비용들 중 적은 값을 x와 더하여 저장 해주는 과정이다.
 
 return grid[n_len-1][m_len-1]
 
 #결과
 #1 4 5
 #2 7 12
 #4 6 7
 #이렇게 결과가 작성이 된다