#9701. Bee Route / 蜜蜂路线
Bee Route / 蜜蜂路线
Problem 8: Bee Route / 蜜蜂路线
版权信息: CSP-S
任务总览
任务名称 | 时间限制 | 内存限制 | 分数 |
---|---|---|---|
蜜蜂路线 | 1 sec | 1024 MB | 5 points |
题目描述
一只蜜蜂在数字蜂房上爬动,已知它只能从标号小的蜂房爬到标号大的相邻蜂房,现在问你:蜜蜂从蜂房M开始爬到蜂房N,M < N,有多少种爬行路线?
编程任务: 给定整数M和N,计算蜜蜂从蜂房M到蜂房N的不同路径数。
输入格式
输入包含两个整数M和N,表示蜜蜂从蜂房M开始,爬行到蜂房N。保证M < N,且M和N为正整数。
输出格式
输出一个整数,表示从蜂房M到蜂房N的不同路径数。
输入输出示例
输入示例 1
1 14
输出示例 1
377
时间复杂度分析
步骤 | 复杂度 |
---|---|
动态规划计算路径数 | O(n) |
总复杂度 | O(n) |
本题可以通过动态规划来求解,从M到N的路径数可以通过递推的方式从底向上计算出来。