初级DP（简单递推）3水题

01 母牛的故事

Description

有一头母牛，它每年年初生一头小母牛。每头小母牛从第四个年头开始，每年年初也生一头小母牛。请编程实现在第n年的时候，共有多少头母牛？

Input

输入数据由多个测试实例组成，每个测试实例占一行，包括一个整数n(0<n<55)，n的含义如题目中描述。
n=0表示输入数据的结束，不做处理。

Output

对于每个测试实例，输出在第n年的时候母牛的数量。
每个输出占一行。

Sample Input

Sample Output

2
4
6

题目大意 ：题意简单明了，不再做解释稍稍变形的 菲波那切数列 
         dp[i]=dp[i-1]+dp[i-3];
  数据也比较小，int就够用

 1 #include <iostream>
 2 #include<stdio.h>
 3 #include<algorithm>
 4 #include<ctype.h>
 5 #include<string.h>
 6 #include<math.h>
 7 #include<stdlib.h>
 8 #include<vector>
 9 #include<queue>
10 using namespace std;
11 #define oo 0x3f3f3f3f
12 #define N 1010000
13 
14 
15 int main()
16 {
17     int n;
18 
19     int dp[110];
20     memset(dp,0,sizeof(dp));
21     dp[1]=1;
22     dp[2]=2;
23     dp[3]=3;
24     dp[4]=4;
25     for(int i=5;i<=55;i++)
26     {
27         dp[i]=dp[i-1]+dp[i-3];
28     }
29     while(scanf("%d",&n),n)
30     {
31         printf("%d
",dp[n]);
32     }
33     return 0;
34 }

02 一只小蜜蜂...（hdu 2044）

Description

有一只经过训练的蜜蜂只能爬向右侧相邻的蜂房，不能反向爬行。请编程计算蜜蜂从蜂房a爬到蜂房b的可能路线数。
其中，蜂房的结构如下所示。

Input

输入数据的第一行是一个整数N,表示测试实例的个数，然后是N 行数据，每行包含两个整数a和b(0<a<b<50)。

Output

对于每个测试实例，请输出蜜蜂从蜂房a爬到蜂房b的可能路线数，每个实例的输出占一行。

Sample Input

2
1 2
3 6

Sample Output

1
3

题目大意：如题

简单递推，如：1->4可通过3->4 or 2->4
              so dp[i]=dp[i-1]+dp[i-2];

 1 #include <iostream>
 2 #include<stdio.h>
 3 #include<algorithm>
 4 #include<ctype.h>
 5 #include<string.h>
 6 #include<math.h>
 7 #include<stdlib.h>
 8 #include<vector>
 9 #include<queue>
10 using namespace std;
11 #define oo 0x3f3f3f3f
12 #define N 1010000
13 
14 
15 int main()
16 {
17     int n,T;
18     scanf("%d",&T);
19 
20     long long dp[110];
21     memset(dp,0,sizeof(dp));
22     dp[0]=0;
23     dp[1]=1;
24     dp[2]=2;
25     for(int i=3;i<=55;i++)
26     {
27         dp[i]=dp[i-1]+dp[i-2];
28     }
29     while(T--)
30     {
31         int a,b;
32         scanf("%d%d",&a,&b);
33         n=b-a;
34         printf("%I64d
",dp[n]);
35     }
36     return 0;
37 }

03 超级楼梯

Description

有一楼梯共M级，刚开始时你在第一级，若每次只能跨上一级或二级，要走上第M级，共有多少种走法？

Input

输入数据首先包含一个整数N，表示测试实例的个数，然后是N行数据，每行包含一个整数M（1<=M<=40）,表示楼梯的级数。

Output

对于每个测试实例，请输出不同走法的数量

Sample Input

2
2
3

Sample Output

1
2
题目大意：如题。

逆向思维，最后一次只能是1或2，所以即
                          dp[n]=dp[n-2]+dp[n-1];
还是斐波那契数列。

#include <iostream>
#include<stdio.h>
#include<algorithm>
#include<ctype.h>
#include<string.h>
#include<math.h>
#include<stdlib.h>
#include<vector>
#include<queue>
using namespace std;
#define oo 0x3f3f3f3f
#define N 1010000


int main()
{
    int n,T;
    scanf("%d",&T);

    int dp[110];
    memset(dp,0,sizeof(dp));
    dp[0]=0;
    dp[1]=1;
    dp[2]=2;
    for(int i=3;i<=44;i++)
    {
        dp[i]=dp[i-1]+dp[i-2];
    }
    while(T--)
    {
        scanf("%d",&n);
        printf("%d
",dp[n-1]);
    }
    return 0;
}