动态规划之数楼梯

这题有很多方法都可以写；
如果用递归，可以拿一半的分。这道题主要是考两个知识点；

1. 动态规划
2. 高精度

思路：

1阶楼梯有1种方案，2阶楼梯有两种方案。3阶楼梯有3种方案，4阶楼梯有5种方案，。。相信到这里细心的道友已经发现，这就是小学学的斐波那契数列。但是为什么是这样呢？

假设n阶楼梯，要计算n阶楼梯的行走方案。由于走到第n阶楼梯的前一步有两种情况，要么是从n-1阶楼梯走一阶上来，要么从n-2阶楼梯走两阶楼梯上来。那么求n阶楼梯的行走方案，实际上就变成了走n-2阶楼梯的方案数加上走n-1阶楼梯的方案数之和。其中满足n>=2.这样就可以证明使用斐波那契数列的合理性。

这种方式不就是动态规划的核心思想：解决大问题，就是不断解决小问题，最后解决大问题？

根据这个原理，我们可以写出代码

#include
using namespace std;
int f[10000];

void Dynamic()
{
	f[1]=1;
	f[2]=2;
	for(int i=3;i<=n;i++)
		f[i]=f[i-1]+f[i-2];
}
int main()
{
	int n;
	cin>>n;
	if(n==1)
	{
		printf("1");
		return 0;
	}
	Dynamic();
	cout< 
看样子好像没有什么问题，但是这样只有50分，因为当n很大的时候，f[n]会大到没有内置类型可以存放答案。那么第二个问题来了
 
高精度！！（大数相加)
 
见代码：(满分未优化）
 
#include
using namespace std;
int n;
int a[10000];
int b[10000];
int a_len = 1;
int b_len = 1;
void add(int* a, int* b,int k)
{
	int c[10000];
	int max = (a_len >= b_len) ? a_len : b_len;
	int min = (a_len >= b_len) ? b_len : a_len;
	int i = 1;
	int j = 1;
	int jinwei = 0;
	for (i; i <= max; i++)
	{
		int temp = (a[i] + b[i] + jinwei) / 10;
		c[i] = (a[i] + b[i] + jinwei) % 10;
		jinwei = temp;
	}
	while(jinwei > 0)
	{
		c[i++] = jinwei % 10;
		jinwei /= 10;
	}
	if (k ==1)
	{
		for (int j =1; j
			a[j] = c[j];
		}
		a_len = i - 1;
	}
	else   //k==0
	{
		for (int j = 1; j < i; j++)
		{
			b[j] = c[j];
		}
		b_len = i - 1;
	}
}

void Dynamic()
{
	a[1] = 1;
	b[1] = 2;
	for (int i=1;i<=n-2;i++)
	{
		if (i % 2 == 1)
			add(a, b,1);
		else
			if (i % 2 == 0)
				add(a, b,0);
	}
}
int main()
{
	cin >> n;
	if (n == 1)
	{
		printf("1");
		return 0;
	}
	Dynamic();
	if ((n - 2) % 2 == 1)
	{
		for (int i = a_len; i >= 1; i--)
			printf("%d", a[i]);
	}
	else
	{
		for (int i = b_len; i >= 1; i--)
			printf("%d", b[i]);
	}
	return 0;
}