문제
풀이
DP와 Top-down 방식의 재귀함수를 활용하여 풀어줬습니다. 다음은 재귀함수 코드입니다.
1
2
3
4
5
6
7
8
9
10
11
int getMin(vector<vector<int>>& grid, int y, int x){
// 기저 사례
if(y==0 && x==0) return grid[0][0];
if(y<0 || x<0) return 987654321;
// Memoization
int &ret = cache[y][x];
if(ret!=-1) return cache[y][x];
return cache[y][x] = grid[y][x] + min(getMin(grid,y-1,x), getMin(grid,y,x-1));
}
cache 배열에 memoization을 수행해줍니다. cache 에 값이 할당 된 적 있다면 바로 cache 값을 return 해줍니다.
아니라면 현재 위치의 grid 값에 위의 cache값과 왼쪽의 cache 값의 최소 값을 더해주며 갱신해줍니다.
1
2
3
4
5
// Memoization
int &ret = cache[y][x];
if(ret!=-1) return cache[y][x];
return cache[y][x] = grid[y][x] + min(getMin(grid,y-1,x), getMin(grid,y,x-1));
코드 효율도 꽤 괜찮은 성능을 보입니다.
코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
int cache[200][200];
int getMin(vector<vector<int>>& grid, int y, int x){
// 기저 사례
if(y==0 && x==0) return grid[0][0];
if(y<0 || x<0) return 987654321;
// Memoization
int &ret = cache[y][x];
if(ret!=-1) return cache[y][x];
return cache[y][x] = grid[y][x] + min(getMin(grid,y-1,x), getMin(grid,y,x-1));
}
int minPathSum(vector<vector<int>>& grid) {
int n = grid.size()-1, m = grid[0].size()-1;
memset(cache, -1, sizeof(cache));
return getMin(grid,n,m);
}
};
