C++ 64. Minimum Path Sum(Leet Code)

Leet Code_64. Minimum Path Sum

Dynamic Programming

 

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

 

문제 해석

 

이 문제를 풀기위해 이해해야 할 내용은 다음과 같습니다.

 

목표

Start부터 Finish 까지 갈수있는 경로중 가장 적은 비용이 드는 경로의 비용 구하기

​

방법

1. Start부터 Finish 까지 갈수있는 경로중 가장 적은 비용이 드는 경로의 비용 구하기

 

결과

Start부터 Finish 까지 갈수있는 경로중 가장 적은 비용이 드는 경로의 비용 구하기

 

통과한 코드

class Solution {
public:
    int minPathSum(vector<vector<int>>& grid) {
        vector<vector<int>> vec = grid;
    int col = grid[0].size();
    int row = grid.size();
    for (int i = 1; i < row; i++)
    {
        vec[i][0] = vec[i - 1][0] + grid[i][0];
    }
    for (int i = 1; i < col; i++)
    {
        vec[0][i] = vec[0][i-1] + grid[0][i];
    }
    for (int j = 1; j < col; j++)
    {
        for (int i = 1; i < row; i++)
        {
            vec[i][j] = min(vec[i - 1][j] , vec[i][j - 1]) + grid[i][j];
        }
    }
    return vec[row - 1][col - 1];
    }
};

이전에 풀었던 아래 링크와 비슷한 문제.

이전 문제는 경로를 구하는 거라면 이번 문제는 최소 비용 경로의 값을 구하는 문제

이전 경로까지의 비용 중 작은 비용에 현재위치의 비용을 더하는 방식으로 처리하여 풀었더니 해결!

https://dev-su.tistory.com/50

C++ 62. Unique Paths(Leet Code)