Leetcode[day18] - Minimum Path Sum

Given a m x n grid filled with non-negative numbers, find a path from top left to bottom right which minimizes the sum of all numbers along its path.

Note: You can only move either down or right at any point in time.

Input:
[  
[1,3,1],
[1,5,1],
[4,2,1]
]
Output: 7
Explanation: Because the path 1→3→1→1→1 minimizes the sum.

1. 알고리즘을 해결하기 위해서 생각한 방법

 

 - 최소값을 구해야하니, Math.min()을 활용해야 한다고 생각이 들었다.

 - 누적된 길이를 구해야하니, 해당 배열의 누적값을 이용해야 한다고 생각이 들었다.

 - Math.min(grid[row-1][col] + grid[row][col], grid[row][col-1] +grid[row][col])

왼쪽, 오른쪽의 최소값일 거라고 생각했다.

 

2. 알고리즘 작성 중, 어려운 점

 

 - 없었다.

 

3. 내가 작성한 알고리즘

 

class Solution {
    public int minPathSum(int[][] grid) {
        for(int i=0; i<grid.length; i++){
            for(int j=0; j<grid[i].length; j++){
                explore(grid, i, j);
            }
        }
        return grid[grid.length - 1][grid[grid.length-1].length - 1];
    }
    
    private void explore(int[][] grid, int row, int col){
        if(row == 0 && col == 0){
            
        }
        else if(row == 0){
        	//왼쪽에 붙어 위에서 밑으로 가는 경우
            grid[row][col] = grid[row][col-1] + grid[row][col]; 
        }else if(col == 0){
        	//위에 붙어 왼쪽에서 오른쪽으로 가는 경우
            grid[row][col] = grid[row-1][col] + grid[row][col];
        }else{
            grid[row][col] = Math.min(grid[row][col-1]+grid[row][col], 
                                     grid[row-1][col]+grid[row][col]);
        }
    }
}

 

4. 내가 작성한 알고리즘 결과

 

 

문제 : https://leetcode.com/explore/challenge/card/30-day-leetcoding-challenge/530/week-3/3303/

Explore - LeetCode