分析 > 题目：如图，小码君站在A点，他想去找小码酱玩，小码酱在B点。小码君的行走是有规则的：可以向下、或者向右。 > 同时小码酱在棋盘上的任一点放了一个的马（如上图的C点），该马所在的点和所有跳跃一步可达的点称为马的控制点。例如上图C点上的马可以控制9个点（图中的P1，P2...P8和C）。小码君不能通过对方的控制点。 > 棋盘用坐标表示，A点（0，0）、B点（n, m）(n,m为不超过20的整数，并由键盘输入)，同样马的位置坐标是需要给出的（约定：C!=A，同时C!=B）。现在要求你计算出小码君从A点能够到达B点的路径的条数。 思路 本题可以使用二维动态规划，先标记出每个控制点，然后再遍历所有点进行累加路径。因为只能往右和下，所以能到一个点的路径就是上面一格路径数量加上左边数量的和，得到状态转移方程：dp[i][j]=max(dp[i][j],dp[i−1][j]+dp[i][j−1])dp[i][j] = max(dp[i][j],dp[i-1][j] + dp[i][j-1])dp[i][j]=max(dp[i][j],dp[i−1][j]+dp[i][j−1])。注意，鉴于指数级累加，本题相关数据必须使用 longlonglong longlonglong 类型。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 代码 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 2024年12月08日 版本1