[LeetCode 62 Unique Paths] 동적 계획 계산 경로

1143 단어 알고리즘분할 알고리즘
문제 설명
m * n 의 격자 를 지정 합 니 다. 시작 점 은 격자 의 가장 왼쪽 위 이 고 종점 은 격자 의 가장 오른쪽 아래 입 니 다. 한 로봇 은 아래 와 오른쪽으로 만 이동 할 수 있 습 니 다. 로봇 이 시작 점 에서 종점 까지 모두 몇 가지 중복 되 지 않 는 경 로 를 구 해 야 합 니 다.문제 의 입력 은 격자 의 길이 m 와 너비 n 이 고 출력 은 서로 다른 경로 의 수량 입 니 다.
2. 사고 분석
이 문 제 는 동적 으로 계획 하 는 방법 이 매우 간단 하 다. 로봇 이 출발점 부터 격자 안의 모든 칸 의 서로 다른 경로 수 를 계산 하고 경로 수량 을 같은 크기 의 m * n 의 행렬 에 저장 하면 우 리 는 종점 에 대응 하 는 행렬 값 만 출력 하면 된다.경로 중의 모든 격자 에 대해 로봇 은 격자 위 나 격자 왼쪽 을 거 쳐 격자 에 도착 할 수 있다. 행렬 M 에 대응 하면 우 리 는 M [i] [j] = M [i - 1] [j] + M [i] [j - 1] 을 뚜렷하게 얻 을 수 있다. 격자 맨 위 와 격자 맨 왼쪽 은 모두 하나의 경로 만 도착 하기 때문에 M [0] [j] = 1 과 M [i] [0] = 1 이 있다. 그 중에서 i, j 는 m, n 이내 의 모든 숫자 를 나타 낸다.이 두 가지 공식 에 따 르 면 우 리 는 로봇 이 모든 격자 에 도착 하 는 경로 수 를 추정 할 수 있다. 즉, 완전한 행렬 M 값 을 얻 고 M [m - 1] [n - 1] 을 출력 하면 된다.
3. 코드 구현
class Solution {
public:
    int uniquePaths(int m, int n) {
       vector> result(m,vector (n,1));
        for(int i = 1; i < m;i++) {
            for(int j = 1; j < n;j++) {
                result[i][j] = result[i - 1][j] + result[i][j - 1];
            }
        }
        return result[m-1][n-1];
    }
};
toString 방법 정보
[Ruby] Gem:FilePermissionError

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
best100-homepage