Leet Code - 64. Minimum Path Sum

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

Minimum Path Sum - LeetCode

 

Answer

 

처음엔 우측 혹은 아래쪽만 체크를하고 작은값으로만 greedy한 방식으로 가면 풀 수 있을거라 생각하고

다음과 같이 수식을 짰었다.

 

dp: MxN 그리드에서 목적지에 도달할 때 합이 최소가 되는 Path

dp[x] = 이전 dp[x-1]에서 갈 수 있는 가장 작은 값

 

 그런데 이렇게 수식을 짜보니 당장 문제에 나온 배열만해도 풀리지가 않았다

 

 

그래서 새로 dp[i][j]를 정의하고 다음과 같이 풀었다.

dp[i][j] = grid[i][j]의 위치에 있을 때 Path 값의 최솟값이라 가정했다.

dp[i][j] = grid[i][j] + min(dp[i][j-1], dp[i-1][j])라고 식을 세워보니

 

i = 0일때와 j = 0일 때 에러가 나서 처리해주었다.