Path Problems

Path Problems

A robot starts at the upper-left corner $(0,0)$ of an m-by-n grid. Each move goes one cell down or right. How many ways lead to the bottom-right corner?

Whatever route reaches the lower-right corner, it has a last move. The destination is $(m-1,n-1)$, so the previous cell must be $(m-2,n-1)$ or $(m-1,n-2)$.

If X routes reach $(m-2,n-1)$ and Y routes reach $(m-1,n-2)$, then X + Y routes reach $(m-1,n-1)$. The original problem becomes counting routes to those two preceding cells.

This gives f[i][j] = f[i−1][j] + f[i][j−1], where f[i][j] counts the ways to reach $(i,j)$.

Initially, f[0][0] = 1: there is one way to be at the starting cell.

On a boundary where i = 0 or j = 0, only one direction can lead to the cell, so f[i][j] = 1.

Path problem

#include <stdio.h>

int path(int row, int col) {
    int path[row][col];
    for (int i = 0; i < row; i++) {
        for (int j = 0; j < col; j++) {
            if (i == 0 || j == 0) {
                path[i][j] = 1;
            } else {
                path[i][j] = path[i - 1][j] + path[i][j - 1];
            }
        }
    }
    return path[row - 1][col - 1];
}

int main(void) {
    printf("%d\n", path(4, 8));
    return 0;
}

Row and column counts are positive integers. Counts for the examples fit the integer range.