#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的路径数可以通过递推的方式从底向上计算出来。