Leetcode 64) Minimum Path Sum

29 Jul 2021 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)
        */
    }
}