路径问题

路径问题

有一个机器人位于一个m行n列的网格的左上角$(0, 0)$，机器人每次只能向下或向右移动一步，问有多少种方法可以走到右下角。

无论机器人用何种方式到达右下角，总有最后挪动的一步。右下角的坐标为$(m-1, n-1)$，那么前一步机器人一定在$(m-2, n-1)$或$(m-1, n-2)$的位置。

如果机器人有X种方式从左上角走到$(m-2, n-1)$，有Y种方式从左上角走到$(m-1, n-2)$，那么机器人一共有X + Y种方式从左上角走到$(m-1, n-1)$。原问题就转换为了机器人有多少种方式从左上角走到$(m-2, n-1)$和$(m-1, n-2)$。

那么可以得出转移方程f[i][j] = f[i-1][j] + f[i][j-1]，其中f[i][j]表示机器人有多少种方式走到$(i, j)$。

初始条件为f[0][0] = 1，因为机器人只有1种方式到达左上角。

边界情况为当i = 0或j = 0，则前一步只能有一个方向到达，因此f[i][j] = 1。

路径问题

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

网格行数和列数均为正整数，示例范围内路径数量不溢出。