2차원 배열의 경로 수 계산(그리드 Traveller) (Count number of paths on 2d-array (grid Traveller))

문제 설명

2차원 배열의 경로 수 계산(그리드 Traveller) (Count number of paths on 2d‑array (grid Traveller))

나는 다음과 같은 목표를 가지고 있다: "2차원 m x n 행렬이 주어지면 왼쪽 상단 모서리에서 오른쪽 하단 모서리까지 가능한 모든 경로를 계산하는 알고리즘을 작성하십시오. 오른쪽으로 이동하거나 아래로 이동하는 두 가지 방향으로만 이동할 수 있습니다.' 문제는 분해하기가 매우 쉽습니다. 예를 들어 3 x 3 그리드에는 2 x 3 그리드와 3 x 2 그리드를 합친 만큼의 경로가 있습니다. 따라서 재귀 솔루션은 매우 직관적입니다.

저는 재귀 솔루션과 메모이제이션 솔루션(2차원 배열이 이미 계산된 경로를 저장하는 경우)을 구현했습니다. C에서는 그리드가 너무 커지면 두 함수 모두 여전히 동일하지만 음수 솔루션을 반환합니다(즉, 15 x 15는 제대로 작동하지만 18 x 18은 더 이상 작동하지 않음). 이게 어디서 왔는지 아세요? 내 코드는 아래에 첨부되어 있습니다. 또한.. Memoization 솔루션의 배열을 코딩하는 좋은 방법이 있습니까? A[m][n]을 함수 매개변수로 사용하면 제대로 작동하지 않으므로 잠시 하드코딩했습니다.

고마워요!</ 피> 6

#include <stdio.h>

int gridTravel(int m, int n){
    if (m == 0 || n == 0){
        return 0;
    }
    if (m == 1 || n == 1){
        return 1;
    }
    return gridTravel(m‑1, n) + gridTravel(m, n‑1);
}

int gridTravelMemo(int m, int n, int A[15][15]){
    if (m == 0 || n == 0){
        return 0;
    }
    if (m == 1 || n == 1){
        return 1;
    }
    if (A[m‑1‑1][n‑1] == 0){
        A[m‑1‑1][n‑1] = gridTravelMemo(m‑1, n, A);
    }
    if (A[m‑1][n‑1‑1] == 0){
        A[m‑1][n‑1‑1] = gridTravelMemo(m, n‑1, A);
    }
    return  A[m‑1‑1][n‑1] + A[m‑1][n‑1‑1];
}

int main(){
    int res = gridTravel(15,15);
    printf("There is a total of %d ways to traverse the grid (Grid size is 15 by 15).\n", res);

    int res2 = gridTravel(18,18);
    printf("There is a total of %d ways to traverse the grid (Grid size is 18 by 18).\n", res2);

    int A[15][15] = {0};
    int res_memo = gridTravelMemo(15,15,A);
    printf("There is a total of %d ways to traverse the grid (Grid size is 15 by 15).\n", res_memo);

    return 0;
}

참조 솔루션

방법 1:

I wouldn't use any dynamic programming or recursion here, but would rather solve it using combinatorics.

As noted by @Eric Postpischil, you should use a wider type like uint64_t or unsigned long long or similar, when calculating the number of paths.

Explanation

What you are asked is how may paths of length m ‑ 1 + n ‑ 1 there are such that they start at the top left point and end at the bottom right point. Why m + n ‑ 2?

Well, because you can only move either to the right or downwards. Initially, you are m ‑ 1 rows and n ‑ 1 columns away form the target. With each step, you're getting 1 row or 1 column closer to the target. So, you need to take exactly m + n ‑ 2 steps.

But how many combinations are there? Out of m + n ‑ 2 steps, you have to take exactly m ‑ 1 steps downwards and n ‑ 1 steps to the right. So, the number of ways to take m ‑ 1 vertical steps(or n ‑ 1 horizontal steps) out of m + n ‑ 2 steps is Cm‑1m+n‑2 or Cn‑1m+n‑2 (please take a look at the definition of Binomial coefficient here if needed).

Formula

Both of the formulas below produce the same result

Cm‑1m+n‑2

Cn‑1m+n‑2

Code

Then, your method could be re‑implemented as below. Please note that you may experience an overflow if n and m become relatively big. Also, my implementation for a binomial coefficient is not the most optimal.

#define MIN(a,b) (((a)<(b))?(a):(b))

uint64_t gridTravel(uint64_t m, uint64_t n) {
    if (m == n && m == 1) {
        return 0;
    }

    uint64_t result = 1;
    for (uint64_t i = 1; i <= MIN(m ‑ 1,n ‑ 1); i++) {
        result *= (m + n ‑ 1 ‑ i);
        result /= i;
    }

    return result;
}

방법 2:

use long variable type for res and res1 inplace of int type.

the recurssive finding overruns the int limits.

(by cactus_splines、Anatolii、hsuecu)

참조 문서

1. Count number of paths on 2d‑array (grid Traveller) (CC BY‑SA 2.5/3.0/4.0)