64. Minimum Path Sum

64. Minimum Path Sum

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

문제

풀이(DFS)

DFS로 나타낸 경로이다.

오른쪽 길, 아래쪽 길이 막히지 않는 이상 갈 수 있는 경로는 오른쪽, 아래쪽 2가지가 있다. 즉 오른쪽, 아래쪽을 비교해서 최소값을 찾는 알고리즘으로 구현하였다.

오른쪽 길이 막히지 않고, 아래쪽 길이 막히지 않았을 때 right_path(오른쪽), down_path(아래)를 비교해서 최소값을 리턴하는 구조이다.

결과

풀이(DP)

DP로 나타낸 표이다.

dp[1][1]일 때에는 출발 지점이니 1로 둔다.
dp[1][2]일 때에는 올 수 있는 경로가 right로 올 때, down으로 올 때이므로 이 중 최소값을 구한다. 즉 min(1, inf) + 현재값(3) => 4가 된다.
마찬가지로 dp[1][3] => min(4, inf) + 1 => 5
dp[2][1] = min(inf, 1) + 1 => 2
이런식으로 최소값을 dp에 저장하면서 찾아가면 된다.

결과