[DP] Minimum Path Sum

2차원 배열이 주어졌을때, 왼쪽위에서 오른쪽아래까지 가는 최소경로에 해당하는 vaule들을 모두 합하여 리턴하는 문제

역시 전형적인 점화식문제다

 

각 element를 기준으로 최소합을 구한다.

이 방식이 근본적인 Dynamic Programming 기법이다.

이때 i가0, j가 0인 경우는 각각 i-1, j-1이 없으므로 바로 이전 값을 더한것이 최소값이 된다.