[LeetCode 64 최소 경로 Sum] 동적 계획 계산 경로
m * n 의 사각형 을 지정 합 니 다. 그 중에서 모든 사각형 에 숫자 가 있 습 니 다. 지금 은 사각형 의 가장 왼쪽 위 에서 가장 오른쪽 아래로 이동 합 니 다. 매번 이동 할 때마다 아래 에서 이동 하거나 오른쪽으로 이동 할 수 밖 에 없습니다.모든 경로 가 하나의 경로 와 개념 에 대응 합 니 다. 즉, 이 경로 의 모든 격자 에 있 는 숫자 와 가장 왼쪽 위 에서 가장 오른쪽 아래 까지 의 모든 경로 에서 경로 와 가장 작은 것 을 구하 고 이 경로 와 출력 해 야 합 니 다.
2. 사고방식 해석
이 문제 의 사고방식 은 비교적 간단 하 다. 똑 같이 동적 기획 사고방식 을 이용 하여 문 제 를 해결 하고 기점 에서 m * n 매트릭스 까지 각 칸 의 가장 짧 은 경로 값 을 계산 하여 m8n 크기 의 매트릭스 path 에 저장 하고 마지막 으로 path [m - 1] [n - 1] 을 출력 하면 된다.모든 격자 는 위 나 왼쪽 격자 만 지나 갈 수 있 기 때문에 이 격자 의 최소 경로 값 은 이 격자 값 에 왼쪽 격자 와 위 격자 중 경로 값 이 작은 것 을 더 하면 공식 path [i] [j] = grid [i] [j] + min (path [i - 1] [j], path [i] [j - 1]) 을 얻 을 수 있 고 공식 에 따라 각 격자 의 최소 경로 값 을 계산 하면 된다.
3. 코드 구현
class Solution {
public:
int minPathSum(vector>& grid) {
int n = grid[0].size();
int m = grid.size();
vector> path(m,vector (n,0));
path[0][0] = grid[0][0];
if(m == 1 && n == 1) return grid[0][0];
for(int i = 1; i < n;i++) {
path[0][i] = path[0][i - 1] + grid[0][i];
}
for(int i = 1; i < m;i++) {
path[i][0] = path[i - 1][0] + grid[i][0];
}
if(m > 1 && n > 1) {
for(int i = 1; i < m; i++) {
for(int j = 1; j < n; j++) {
path[i][j] = grid[i][j] + min(path[i - 1][j],path[i][j - 1]);
}
}
}
return path[m - 1][n - 1];
}
}; 이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
【Codility Lesson3】FrogJmpA small frog wants to get to the other side of the road. The frog is currently located at position X and wants to get to...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
