[Leetcode 30/100] Minimum Path Sum - Medium

leetcode.com/problems/minimum-path-sum/

Minimum Path Sum - LeetCode

Leetcode 30번째 풀이 글인데, 사실 포스팅 안한거까지 80문제 정도 풀었다.. 앞으로는 포스팅을 꾸준히 해서 100문제를 빨리 채우려고 한다.

이 문제는 재귀 풀이 방식을 통한 풀이로 TLE가 났는데, 다이나믹 프로그래밍으로 어떻게 풀이했는지 써보려고 한다.

문제 풀이 방식

Recursrion 풀이

주의할 점

재귀 접근 방식은 basc condition을 정하는 것이 중요하다. [0,0] -> [m,n] 까지 가는 path를 구하는 것이므로 0,0을 base condition으로 설정했다.

이 문제에서 재귀를 호출하여 처음으로 계산을 시작하는 지점은 마지막 도착지이며, 0,0 시작점을 가게 되면 재귀 함수를 리턴하여 종료할 것이다.

추가적으로 맨 좌측과 맨 상단의 경우 이동 방향이 정해져있기 때문에 제약 조건을 걸어주는 것이 함수의 호출 횟수를 줄일 수 있는 방법이 될 것이다.

그리고 min path를 구하는 것이기 때문에 최소 값을 더 해나갈 것이다.

소스코드

recursion

이 코드는 TLE를 볼 수 있는 코드이다. 결국 DP라는 것은 재귀 호출을 줄이는 것이다. 이미 계산한 식은 다시 호출할 필요 캐싱하는 것이 DP의 주 포인트이다.

문제 풀이 방식

다이나믹 프로그래밍 풀이

주의할 점

위의 재귀 방식을 이해했다면 dp는 쉽게 구현할 수 있을 것이다.

주의할 것을 한가지 꼽자면 아무래도 최상단과 맨 좌측의 예외 처리를 말할 수 있을 것 같다.

소스코드