前言
牛客网PAT乙级训练1009
题目描述
nowcoder利用业余时间养了一窝蜜蜂，因为空间比较小，蜂房只有两排，如下图所示：
image
如你所见，蜜蜂的蜂房是正六边形，假设蜜蜂只会从左往右爬，即从1号蜂房能爬到2号和3号；从6号蜂房能爬到7号和8号……
现给出两个蜂房的编号a和b，要求计算蜂房a的蜜蜂爬到蜂房b有几条不同路线。
输入描述
- 输入的第一行是一个整数n
- 接下来n行数据，每行一组测试用例
- 每组测试用例包含两个正整数a和b，(0 < a < b < 2^31)
输出描述
每组用例的结果单独输出一行。输出数据结果范围是 [0, 2^63)。
输入例子
3
1 2
3 6
99 100
输出例子
1
3
1
解析
还是老问题，解决方案参考骨牌铺方格
解决方案
以下是本题的其中一个解法：
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
while (scanner.hasNext()) {
int t = scanner.nextInt();
for (int k = 0; k < t; k++) {
int x = scanner.nextInt();
int y = scanner.nextInt();
System.out.println(getRes(x, y));
}
}
}
private static long getRes(int x, int y) {
int N = y - x + 1;
if (N <= 2)
return 1;
long[] dp = new long[N + 1];
dp[1] = 1;
dp[2] = 1;
for (int i = 3; i <= N; i++)
dp[i] = (dp[i - 2] + dp[i - 1]);
return dp[N];
}
}
