minimum path sum

• 2차원에서 최소 비용으로 가는 해당 위치의 최소 cost를 구하는 문제다.

Algorithm

1 3 1 2  | 1 4  5  7
2 4 5 2  | 3 7  10 9
3 4 5 6  | 6 10 15 15
1 5 6 2  | 7 12 18 17

• 왼쪽에 있던 문제에서 0,0에서 (m-1, n-1)으로 가는 최소 비용을 구하는 것인데, 이는 2차원으로만 표현되었지 계단 문제와 동일하다.
• 오른쪽과 아래쪽 방향으로만 움직인다는 제한이 있으므로 해당 경로 중 가장 적은 cost를 골라 해당 위치에서의 cost를 업데이트해주고, 이는 부분문제가 하나의 큰문제를 해결한 것이고 그 큰 문제는 더 큰문제의 cost를 과거의 최소 비용을 가지고 업데이트 해주는 것이다.
• 결국 Answer는 17이 된다. (m-1, n-1)
• 점화식은 F(x, y) = Cost(x,y) + min(F(x-1,y), F(x, y-1)) 인 것이다.