路径计数2（洛谷P1176题题解，Java语言描述）

题目要求

题目链接

分析

我的思路很简单，因为这个题所有的点都是 ( 1 , 1 ) (1,1) (1,1)开始的，所以直接把数组多开一个边，开一个[n+1][n+1]的数组就行了。

初始化 f [ 1 ] [ 1 ] = 1 f[1][1]=1 f[1][1]=1，先把右边界和上边界的所有值初始化完成，因为它们的值只有一个来源。

之后就遍历所有的点位，按照递推式 f [ i ] [ j ] = f [ i − 1 ] [ j ] + f [ i ] [ j − 1 ] f[i][j] = f[i-1][j] + f[i][j-1] f[i][j]=f[i−1][j]+f[i][j−1]来求解即可。

注意的是怎么表示不可过的点呢？我选择直接在矩阵里赋值其为 − 1 -1 −1，扫到 − 1 -1 −1就把当前值改为 0 0 0，这个 0 0 0代表的可是真正的 0 0 0而不是初始化的 0 0 0。

这个题的输入数据特点：

• 总量不大
• 行数多（也不是特别多）
• 每行值很少

所以Scanner很合适，选就对了。

注意要 m o d 100003 mod100003 mod100003，在每一次求和之后就行了，因为两数相加位数不可能大幅跃升，所以也不需要担心爆 i n t int int。

AC代码（Java语言描述）

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt(), m = scanner.nextInt();
        int[][] nums = new int[n+1][n+1];
        for (int i = 0; i