P4725 移动路线（基础）

解题思路

第一步：看懂题目。 蚂蚁的右脚受伤了，只能向下或向右移动，从左上角 (1,1) 走到右下角 (n,m)，问一共有多少种不同的路线。

第二步：认识二维递推（动态规划）。 这是一个非常典型的二维递推问题。设 ways[i][j] 表示从起点 (1,1) 走到格子 (i,j) 的路线总数。想一想：要到达 (i,j)，蚂蚁的“上一步”只可能是从上面 (i-1,j) 向下走一步，或者从左边 (i,j-1) 向右走一步。因为只能向下或向右，不可能从其他地方到 (i,j)。所以走到 (i,j) 的路线数，就等于走到 (i-1,j) 的路线数加上走到 (i,j-1) 的路线数，即 ways[i][j] = ways[i-1][j] + ways[i][j-1]。

第三步：定好边界条件。 起点 (1,1) 只有 1 种“走法”（原地不动），所以 ways[1][1]=1。第一行的格子 (1,j) 只能一直往右走，所以 ways[1][j] 都是 1；第一列的格子 (i,1) 只能一直往下走，ways[i][1] 也都是 1。这些都会由递推公式自然算出来（因为数组外面是 0）。

第四步：举个例子验证。 2 行 3 列时：ways[2][3] = ways[1][3] + ways[2][2]。ways[1][3]=1，ways[2][2]=ways[1][2]+ways[2][1]=1+1=2，所以 ways[2][3]=1+2=3，与样例一致。再以 3 行 4 列为例：第一行从左到右都是 1；第一列从上到下也都是 1；第二行的格子依次是 1、2、3；第三行的格子依次是 1、3、6，最后 ways[3][4]=6。表里每个格子恰好是它左边和上边两个数相加得到的，就像搭积木一层一层往上垒。

第五步：注意数据大小。 n 和 m 最大都是 20，路线数最多是 C(38,19)，大约是 3.5×10^10，已经超过 int 的范围，所以 ways 数组要用 long long 类型。题目特别说明 1 行 1 列时移动路线数是 1，我们的边界条件正好处理了这种情况。

第六步：为什么递推比暴力列举好？ 递推法（动态规划）与暴力列举法最大的不同是：它把每个格子的答案只计算一遍并保存下来，后面的格子直接复用已有的结果，不会重复计算。因此当格子变多时，这种方法的优势就特别明显。

参考代码

// 移动路线：蚂蚁只能向下或向右，用递推 ways[i][j]=ways[i-1][j]+ways[i][j-1]
#include <iostream>
using namespace std;
int main() {
    int n, m;
    cin >> n >> m;
    long long ways[25][25] = {0};
    ways[1][1] = 1;   // 起点有一种走法
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++) {
            if (i == 1 && j == 1) continue;  // 起点跳过
            ways[i][j] = ways[i-1][j] + ways[i][j-1];
        }
    cout << ways[n][m] << endl;
    return 0;
}

复杂度分析

程序用两层循环把 n×m 个格子的路线数全部算一遍，每个格子做一次加法，时间复杂度是 O(n×m)。n、m 最大都是 20，最多计算 400 个格子，非常快。空间上用一个 25×25 的 long long 二维数组，空间复杂度也是 O(n×m)，很小。