Count number of paths on 2d-array (grid Traveller)

user_14517943 0
Viewed 831

I have the following objective: "Given two dimensional m by n matrix, write an algorithm to count all possible paths from top left corner to bottom-right corner. You are allowed to move only in two directions, move right OR move down." The problem is quite easy to break down. For example a 3 x 3 grid has as many paths as a 2 x 3 grid and 3 x 2 grid combined. So a recursive solution is quite intuitive.

I have implemented a recursive solution and a solution with memoization (where a 2d-Array stores the paths that are already calculated). In C but somehow, when the grid becomes too large, both function still return the same, but negative solutions (i.e. 15 x 15 works fine, 18 x 18, not anymore). Any idea where this comes from? My code is attached below. Also.. is there a nice way to code the Array of the Memoization solution? If I use A[m][n] as a function parameter, it doesn't quite work so I just hard-coded it for the moment.

Thanks!

#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;
}
dynamic-programming recursion c arrays algorithm
2 Answers

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;
}
user_10553950

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

the recurssive finding overruns the int limits.

user_153488550
Related