HDU | 2044 一只小蜜蜂...【动态规划，打表】

动态规划 专题

HDU 2044 一只小蜜蜂…

题目描述

输入输出样例

思路

仔细分析一下题目，发现每个蜂房只可能从左侧或者上侧进入，发现其实就是 Fibonacci 。

另外，不管起始、终止位置在哪，都可以等价于从 1 到 b-a+1 。

递推关系如下：

dp[i] = dp[i-1] + dp[i-2];

可以直接打表。

代码

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cmath>
#include <cstring>
using namespace std;
long long int dp[10010];  //改成 long long 型，后面大小会超 int 型 int main(){int n;memset(dp,0,sizeof(dp));//dp[0] = 0;dp[1] = 0;dp[2] = 1;dp[3] = 2;for(int i = 4; i < 10010; ++i){dp[i] = dp[i-1] + dp[i-2];} scanf("%d", &n);for(int i = 1; i <= n; ++i){int start,end;scanf("%d%d",&start,&end);printf("%lld\n", dp[end-start+1]);}return 0;
}