P4735 老鼠吃奶酪（基础）

解题思路

老鼠 Jerry 站在迷宫的左下角 (n,1)，奶酪放在 (x,y)。Jerry 每步只能向上或者向右走一格，问从起点到奶酪一共有多少种不同的移动路线。只要两条路线中有一步不同，就算不同的路线。

这同样是一个网格动态规划问题。设 dp[i][j] 表示从起点 (n,1) 走到 (i,j) 的路线数。起点 dp[n][1]=1。因为每一步只能向上或向右走，所以想到达 (i,j)，只能从它下面的格子 (i+1,j) 向上走一步上来，或者从它左边的格子 (i,j-1) 向右走一步过来。于是 dp[i][j] = dp[i+1][j] + dp[i][j-1]。我们按照从下往上、每行从左往右的顺序逐个格子计算，答案就是 dp[x][y]。

举个例子：n=3、m=4，奶酪在 (2,3)。从 (3,1) 出发，需要向上 1 步、向右 2 步，三种顺序分别是"上右右、右上右、右右上"，一共 3 种路线，与样例输出一致。n、m 最大都是 20，路线总数用 long long 保存足够。注意起点和奶酪的坐标都保证在迷宫范围内，且奶酪一定可以从起点按"向上、向右"的方式走到。

参考代码

// 老鼠吃奶酪：从左下角(n,1)每次向上或向右走到奶酪(x,y)，统计不同路线总数
#include <iostream>
int main(){
  long long dp[25][25];
  int n,m,x,y,i,j;
  std::cin>>n>>m;
  std::cin>>x>>y;
  dp[n][1]=1;                  // 起点只有1条路
  for(i=n;i>=1;i--){           // 从下往上推
    for(j=1;j<=m;j++){         // 从左往右推
      if(i==n&&j==1) continue;
      dp[i][j]=0;
      if(i+1<=n) dp[i][j]+=dp[i+1][j];  // 从下面的格子向上走来
      if(j-1>=1) dp[i][j]+=dp[i][j-1];  // 从左边的格子向右走来
    }
  }
  std::cout<<dp[x][y];
  return 0;
}

复杂度分析

遍历 n×m 个格子，每个格子只做常数次加法，所以时间 O(n×m)。空间上用一个 25×25 的数组，是 O(n×m)。n、m 都不超过 20，一共才 400 个格子，运行非常轻松。