动态规划 专题

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;
}