👀 문제
https://leetcode.com/problems/minimum-path-sum/
👊 도전
1. 설계
- DP를 이용한다.
- dp[i][j]는 (i,j)에서 최솟값으로, 왼쪽이나 위에서 작은 값을 선택하고, 내 값을 더한다.
2. 구현
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
/**
*
* @author HEESOO
*
*/
class Solution {
public int minPathSum(int[][] grid) {
if(grid.length==0) return 0;
int m=grid.length;
int n=grid[0].length;
int[][] dp=new int[m][n];
dp[0][0]=grid[0][0]; // 시작점 초기화
for(int i=0;i<m;i++){
for(int j=0;j<n;j++){
if(i==0 && j==0) continue; // 시작점은 패스
// 왼쪽, 위쪽이 둘 다 존재한다면 둘 중 작은 값 선택
if(i-1>=0 && j-1>=0) dp[i][j]=Math.min(dp[i-1][j], dp[i][j-1])+grid[i][j];
// 위쪽만 있다면(i==0)
else if(i-1<0) dp[i][j]=dp[i][j-1]+grid[i][j];
// 왼쪽만 있다면(j==0)
else dp[i][j]=dp[i-1][j]+grid[i][j];
}
}
return dp[m-1][n-1];
}
}
3. 결과
🤟 성공 🤟
DFS로 하고 싶었지만 참았다
4. 설명
- DP를 이용한다
- m, n의 범위를 알려주지 않아서 왠만큼 큰 숫자여도 풀 수 있어야 할 것 같았다. 그래서 DFS는 아니라고 생각했다.
- 모든 경우를 다 따지는 것이 아니라면, 이런 문제는 보통 DP로 풀 수 있다. 따라서 점화식을 어떻게 짤지 생각했다.
- 오른쪽, 아래쪽으로만 이동할 수 있기 때문에 (i,j)에 가기 위해서는 전의 위치가 (i-1,j)이거나 (i,j-1)이어야 한다.
- 이때 합이 최소가 되도록 움직여야 하므로, 이전 값이 작은 것이 좋다.
- 따라서 이전 위치에서 작은 값+내 값이 된다.
- 이를 점화식으로 만들면, dp[i][j]=min(dp[i-1][j], dp[i][j-1])+grid[i][j]
- 이때 i-1, j-1의 인덱스 범위를 생각해야하므로 if, else if, else문으로 경우에 따라 더할 값을 처리하였다.