LeetCode 64 - Minimum Path Sum (Medium)
문제 LeetCode - 64번 풀이 과정 이동 방향이 고정되어 있는 상태에서 목표 지점에 도달하기 위한 최소 비용을 찾는 문제입니다. 각 칸을 하나의 정점으로 생각하면 이동 방향이 오른쪽 혹은 아래로 고정되어 있으므로 이를 그래프로 모델링하여 다익스트라 알고리즘이나 플로이드와 같은 최단 경로 알고리즘을 사용할 수도 있을 것 같습니다. 하지만 그보다 간단하게 동적 계획법 을 활용하여 문제를 해결할 수 있습니다. 만약 dp(x, y) = (x, y)에서 출발해서 (m, n)에 도달 할 수 있는 최단경로 라고 정의한다면 다음과 같은 점화식을 세울 수 있습니다. dp(x, y) = min(dp(x+1, y), dp(x, y+1)) + cost(x, y), 이때 cost는 현재 (x, y) 에서 필요한 비용 평..
2021. 3. 2.
