刷题刷出新高度，偷偷领先！偷偷领先！偷偷领先！ 关注我们，悄悄成为最优秀的自己！

简答题

现有 22 名小朋友，依次编号 1 到 22，22 名小朋友分别按照下图的位置站好。

每名小朋友只能按照图中箭头指向的方向移动。给出两名小朋友的编号 N 和 M（1≤ N ＜ M ≤ 22），请你找出从编号 N 到编号 M 共有多少条不同的路线。

例如：N = 3，M = 7，从编号 3 的位置到编号 7 的位置共有 5 条路线，分别为：（3->5->7），（3->5->6->7），（3->4->5->7），（3->4->5->6->7），（3->4>6->7）。

【输入格式】

输入两个正整数 N 和 M（1 ≤ N < M ≤ 22），分别表示两名小朋友的编号，之间以一个空格隔开。

【输出格式】

输出一个整数，表示从编号 N 到编号 M 共有多少条不同的路线。


【输入样例1】

3 7

【输出样例1】

5

使用微信搜索喵呜刷题，轻松应对考试！

答案：

```#include #include using namespace std;int uniquePaths(int N, int M) vector> dp(23, vector(23, 0));for (int i = 0; i < 23; i++) {dp[i][i] = 1;}for (int len = 2; len <= 22; len++) {for (int i = 1; i + len - 1 <= 22; i++) {int j = i + len - 1;dp[i][j] = dp[i + 1][j] + dp[i][j - 1];}}int res = 0;for (int i = N; i <= M; i++) {res += dp[N][i];}return res;int main() int N, M;cin >> N >> M;cout << uniquePaths(N, M) << endl;return 0;```

解析：

【喵呜刷题小喵解析】：

这个问题可以使用动态规划来解决。我们可以定义一个二维数组dp[i][j]，其中dp[i][j]表示从编号i到编号j的路线数量。

首先，我们可以初始化dp数组，将dp[i][i]设为1，表示从编号i到编号i只有一条路线，即不移动。

然后，我们可以使用动态规划的思想，从长度为2开始，依次计算长度为3、4、...、22的路线数量。对于每个长度len，我们可以从编号1开始，依次计算编号i到编号j（i+len-1=j）的路线数量。根据题目要求，每个小朋友只能按照图中箭头指向的方向移动，因此，从编号i到编号j的路线数量等于从编号i+1到编号j的路线数量加上从编号i到编号j-1的路线数量。

最后，我们可以从编号N开始，依次累加dp[N][i]的值，直到编号M，得到从编号N到编号M的路线数量。

在C++中，我们可以使用vector来定义二维数组dp，并使用循环来计算dp数组的值。在主函数中，我们可以读取输入的两个正整数N和M，并调用uniquePaths函数来计算从编号N到编号M的路线数量，并将结果输出到控制台。
创作类型：
原创

本文链接：现有 22 名小朋友，依次编号 1 到 22，22 名小朋友分别按照下图的位置站好。 每名小朋友只

版权声明：本站点所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明文章出处。

让学习像火箭一样快速，微信扫码，获取考试解析、体验刷题服务，开启你的学习加速器！

分享考题
share