[LeetCode] 64. Minimum Path Sum

https://leetcode.com/problems/minimum-path-sum/description/

Minimum Path Sum - LeetCode

문제 유형 : 다이나믹 프로그래밍

문제 난이도 : Medium

 

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.

 

m * n의 양수 격자가주어진다. 왼쪽 위에서 오른쪽 아래로 갈 때, 최소 비용을 구하여라. 

(한번에 아래나 오른쪽으로만 이동이 가능하다)

 

 

풀이

같은 크기의 dp 테이블을 만들어서 dp[a][b] = 0, 0에서 a, b까지 가는최소비용으로 한다.

0행이나 0열인 경우에는 이전 바로 옆이나 위의 dp 값에서 그 자리의 비용을 더해주면되지만,

그렇지 않은 경우는 위에서 내려오는게 더 값이 낮은지, 아니면 옆에서 건너오는 값이 더 낮은지 비교해준 뒤, 그 자리의 비용을 더해주면 된다.

 

코드(C++)

class Solution {
public:
    int minPathSum(vector<vector<int>>& grid) {
        int m = grid.size();
        int n = grid[0].size();
        vector<vector<int>> dp(m, vector<int>(n, 0));

        dp[0][0] = grid[0][0];

        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){
                if(i == 0 && j == 0){
                    continue;
                }
                else if(i == 0){
                    dp[i][j] = dp[i][j-1] + grid[i][j];
                }
                else if(j == 0){
                    dp[i][j] = dp[i-1][j] + grid[i][j];
                }
                else{
                    dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j];
                }
            }
        }

        return dp[m-1][n-1];
    }
};