C++LeetCode 구현(62.다른 경로)

[LeetCode]62.Unique Paths 다른 경로
A robot is located at the top-left corner of a m x n grid (marked 'Start' in the diagram below).
The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked 'Finish' in the diagram below).
How many possible unique paths are there?

Above is a 7 x 3 grid. How many possible unique paths are there?
Note: m and n will be at most 100.
Example 1:
Input: m = 3, n = 2
Output: 3
Explanation:
From the top-left corner, there are a total of 3 ways to reach the bottom-right corner:
1. Right -> Right -> Down
2. Right -> Down -> Right
3. Down -> Right -> Right
Example 2:
Input: m = 7, n = 3
Output: 28
이 문 제 는 모든 다른 경로 의 개 수 를 구 하 게 만 들 었 다.처음에 블 로 거들 을 난처 하 게 만 들 었 다.예전 에 이런 문 제 를 겪 어 본 적 이 없 는 것 같 아서 손 쓸 수 없 는 느낌 이 들 었 다.인터넷 에서 공략 을 찾 은 후에 야 문득 크게 깨 달 았 는데,알 고 보 니 이것 은 이전 과 그 랬 구나.  Climbing Stairs  비슷 하 다.그 문 제 는 매번 한 칸 이나 두 칸 씩 올 라 갈 수 있다 는 것 이다.정상에 도달 하 는 모든 다른 기어 오 르 는 방법의 개 수 를 물 어 보 는 것 이다.이 문 제 는 매번 아래로 내 려 가 거나 오른쪽으로 갈 수 있 으 며,가장 오른쪽 아래 에 있 는 모든 다른 주 행 법의 개 수 를 구 하 는 것 이다.그러면 사다리 오 르 기 문제 와 마찬가지 로 동적 계획 Dynamic Programming 으로 풀 어야 합 니 다.2 차원 배열 dp 를 유지 할 수 있 습 니 다.그 중에서 dp[i][j]는 현재 위치 가 다른 주 법의 개 수 를 표시 한 다음 에 상태 이전 방정식 을 얻 을 수 있 습 니 다.  dp[i][j]=dp[i-1][j]+dp[i][j-1],여 기 는 공간 을 절약 하기 위해 1 차원 배열 dp 를 사용 합 니 다.한 줄 한 줄 새로 고침 도 가능 합 니 다.코드 는 다음 과 같 습 니 다.
해법 1:

class Solution {
public:
    int uniquePaths(int m, int n) {
        vector<int> dp(n, 1);
        for (int i = 1; i < m; ++i) {
            for (int j = 1; j < n; ++j) {
                dp[j] += dp[j - 1]; 
            }
        }
        return dp[n - 1];
    }
};

이 문 제 는 사실 또 다른 수학 적 해법 이 있 습 니 다.실제 로봇 이 모두 m+n-2 보 를 걷 는 것 과 같 습 니 다.그 중에서 m-1 보 는 오른쪽으로 가 고 n-1 보 는 아래로 내 려 가 는 것 과 같 습 니 다.그러면 모두 다른 방법 개 수 는 걸음 수 에서 m-1 과 n-1 중 작은 수의 취 법 에 해당 합 니 다.실제 적 으로 조합 수의 문제 입 니 다.코드 는 다음 과 같 습 니 다.
해법 2:

class Solution {
public:
    int uniquePaths(int m, int n) {
        double num = 1, denom = 1;
        int small = m > n ? n : m;
        for (int i = 1; i <= small - 1; ++i) {
            num *= m + n - 1 - i;
            denom *= i;
        }
        return (int)(num / denom);
    }
};

C++구현 LeetCode(62.서로 다른 경로)에 관 한 이 글 은 여기까지 소개 되 었 습 니 다.더 많은 관련 C++구현 서로 다른 경로 내용 은 우리 의 이전 글 을 검색 하거나 아래 의 관련 글 을 계속 조회 하 시기 바 랍 니 다.앞으로 많은 응원 바 랍 니 다!