首页 > ACM题库 > HDU-杭电 > hdu 2563 统计问题-递推-[解题报告]C++
2014
02-10

hdu 2563 统计问题-递推-[解题报告]C++

统计问题

问题描述 :

在一无限大的二维平面中,我们做如下假设:
1、  每次只能移动一格;
2、  不能向后走(假设你的目的地是“向上”,那么你可以向左走,可以向右走,也可以向上走,但是不可以向下走);
3、  走过的格子立即塌陷无法再走第二次;

求走n步不同的方案数(2种走法只要有一步不一样,即被认为是不同的方案)。

输入:

首先给出一个正整数C,表示有C组测试数据
接下来的C行,每行包含一个整数n (n<=20),表示要走n步。

输出:

首先给出一个正整数C,表示有C组测试数据
接下来的C行,每行包含一个整数n (n<=20),表示要走n步。

样例输入:

2
1
2

样例输出:

3
7

思路:赤裸裸的递推问题,设第n步的走法为F(n),往上走的步数为a(n),往左或往右走的步数为b(n);

所以F(n)=a(n)+b(n);接下来分别找前一个状态。因为不能往下走,所以向上走的步数只有一种选择就是上一次的步数相加:a(n)=a(n-1)+b(n-1)(前(n-1)步内往上走的步数+前(n-1)步内往左或右的步数);又因为走过的不能返回,所以往左或右走只有一种方法,但向上走可以是左上和右上两种,因此b(n)=2*a(n-1)+b(n-1);化简得F(n)=2*F(n-1)+F(n-2);

代码一:

#include <stdio.h>
int main()
{
    int s, n, i, a[21];
    scanf("%d", &s);
    while(s--)
    {
        a[1] = 3;
        a[2] = 7;
        scanf("%d", &n);
        for(i = 3; i <= 20; i++)
            a[i] = 2 * a[i - 1] + a[i - 2];
        printf("%d\n", a[n]);
    }
    return 0;
}

内存使用了200多k,于是想着优化

#include <stdio.h>
int main()
{
	int s, n, i, a[3];
	scanf("%d", &s);
	while(s--)
	{
		a[1] = 3;
		a[2] = 7;
		scanf("%d", &n);
		if(n == 1)
			printf("3\n");
		else if(n == 2)
			printf("7\n");
		else
		{
			for(i = 3; i <= n; i++)
				a[i % 3] = 2 * a[(i-1 + 3) % 3] + a[(i-2+3) %3];
			printf("%d\n", a[n%3]);
		}
	}
	return 0;
}

没想到还是200多k,大牛的ok是怎么来的?


解题转自:http://blog.csdn.net/vsooda/article/details/7971853