M'S Blog

M'S Blog

WWDC20 student challenge Winner!

leetcode 64 - Minimum Path Sum

최대 1 분 소요

문제

leetcode 64 - Minimum Path Sum 풀러가기

문제 분석

이 문제는 (0,0)에서 오른쪽 하단으로 가는 경로의 최소 합을 구하는 문제다.

현재 위치를 (i,j)라고 할 때, (i,j)까지의 경로의 최소 합은 모든 경우에 동일 하다. 따라서 Dynamic Programming 으로 풀 수 있다.

현재 위치까지의 최소 합을 d [ i ] [ j ]로 표현하여 점화식을 세운다면

d [ i ] [ j ] = min(d [ i - 1] [ j ] , d [ i ] [ j - 1]) + 현재 위치의 값이 된다.

문제 풀이(C++)

  1. 전체 코드

    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
    30
    31
    32
    33
    34
    35
    #include <algorithm>
     
    class Solution {
    public:
        int minPathSum(vector<vector<int>>& grid) {
            
            if(grid.empty()){
                return 0;
            }        
            
            int n = grid.size();
            int m = grid[0].size();
            
            vector<vector<int>> d(n, vector<int>(m, 0));
            
            return go(grid, d, n-1, m-1);
        }
        int go(vector<vector<int>>& grid, vector<vector<int>>& d, int i, int j){
            
            if(d[i][j] != 0){
                return d[i][j];
            }
            
            if(i==0 && j==0){
                return grid[0][0];
            }else if(i==0){
                d[i][j] = go(grid, d, i, j-1)+grid[i][j];
            }else if(j==0){
                d[i][j] = go(grid, d, i-1, j)+grid[i][j];
            }else{
                d[i][j] = min(go(grid, d, i-1, j), go(grid, d, i, j-1))+grid[i][j];
            }   
            return d[i][j];
        }
    };
    		cs
  • 20번째 줄 : d[ i ] [ j ]의 값이 있다는 것은, 이미 그 위치의 최소 합을 구했다는 것이다. 따라서 그 경우에는 d[ i ] [ j ]를 그대로 반환한다.
  • 24번째 줄 : 0,0일 때는, 그냥 (0,0)에서의 값을 반환하면 된다.
  • 26번째 줄 : i가 0일때는 i-1을 할 수 없으므로 j-1만 할 수 있다.(28번째도 마찬가지)
  • 30번째 줄 : 위에서 말한 점화식을 코딩으로 표현.





아직 배움의 과정에 있는 학생이니 내용에 부족한 점이 보이면 지적은 하되, 비난은 하지 말아주세요!!

댓글남기기

참고