Leetcode 64) Minimum Path Sum
in Algorithms
https://leetcode.com/problems/minimum-path-sum/solution/ 여기에 DP솔루션 아주 잘 나와있다.
내 답안
- 이거 그림으로 보면 이해 확 옴. 혹시 까먹었다면 위에 링크 solution 들어가서 확인!
class Solution {
public int minPathSum(int[][] grid) {
int[][] dp = new int[grid.length][grid[0].length];
dp[0][0]=grid[0][0];
for(int i =1;i<grid.length;i++){
dp[i][0]= dp[i-1][0]+grid[i][0];
}
for(int j =1; j<grid[0].length;j++){
dp[0][j]= dp[0][j-1]+grid[0][j];;
}
for(int i=1 ; i<grid.length;i++){
for(int j=1;j<grid[0].length;j++){
dp[i][j]= Math.min(dp[i-1][j],dp[i][j-1])+grid[i][j];
}
}
return dp[grid.length-1][grid[0].length-1];
}
}
다른 답안
- dp라는 이차원 배열 새로 할당하지 않고, 주어진 grid 배열을 그대로 썼다.
class Solution {
public int minPathSum(int[][] grid) {
for (int j = 1; j < grid[0].length; j++) {
grid[0][j] += grid[0][j-1];
}
for (int i = 1; i < grid.length; i++) {
grid[i][0] += grid[i-1][0];
for (int j = 1; j < grid[0].length; j++) {
grid[i][j] += Math.min(grid[i][j-1], grid[i-1][j]);
}
}
return grid[grid.length-1][grid[0].length-1];
}
}
오답
- Greedy 로 다 해본다. => 당연히 Time Limit뜸..
class Solution {
public int minPathSum(int[][] grid) {
return recursive(0,0,grid,grid[0][0]);
}
public int recursive(int i, int j, int[][]grid, int min){
int a = grid.length;
int b= grid[0].length;
if(i+1==a && j+1==b){
return min;
}
int tournament =Integer.MAX_VALUE;
if(i+1<a){
int tmp = min+grid[i+1][j];
tournament= Math.min(recursive(i+1,j,grid,tmp),tournament);
}
if(j+1<b){
int tmp = min+grid[i][j+1];
tournament= Math.min(recursive(i,j+1,grid,tmp),tournament);
}
return tournament;
/*
(i+1,j)
(i,j+1)
*/
}
}