[수업]최소 비용의 경로를 찾아라

문제

풀이

DP 문제이며, 격자 문제 관련해서 따로 개념 정리한 것이 있으니 그것을 보고 참고하자.

현재(i,j)위치에 오는 경로는 왼쪽, 위밖에 없다.

• 따라서 min((i-1,j), (i,j-1))를 현재 (i,j)위치에 더하면 된다

추가 조건으로 동일 왼쪽,위 값이면 오른쪽경로 이용하라했으니 위에꺼를 택해야 한다.
=> 만약 아래쪽경로 이용하라했으면? 왼쪽꺼를 택해야 한다.

경로는 역추적을 통해서 하면 된다.(비용을 빼가면서 올바른 경로를 찾아가면 됨)