洛谷-P1255-数楼梯

数楼梯 - 洛谷

---

解题思路（50分）：

1.什么时候可以用动态规划呢？

   （1）满足最优子结构-即原问题的最优解包含子问题的最优解

   （2）子问题重叠-需要重复计算某些值的时候，可以将答案存入表格中

   （3）无后效性-求出当前状态的解只和前面有关，不影响后续的值

2.求解爬到n级的台阶的方案数，因为每一步只能走一级或者两级，那么到达n级一定是从n-1或者n-2级台阶上去的，根据加法原理，方案数=到达n-1台阶的方案数+n-2台阶的方案数，依次类推，将一个大问题分成了子问题

3.动态规划的三要素为状态，转移，决策，每一个台阶都是属于一个状态，到达n级台阶的方案数是由n-1和n-2转移而来的，如果用dp数组存方案数的话dp【i】表示到达i级台阶的方案数，状态转移方程即dp【i】=dp【i-1】+dp【i-2】

4.设置初始状态，到达1级台阶的方案数为1，只能上一级，到达2级台阶的方案数为2，一次上两级或者每次上一级，以后的方案数都可求出

---

#include
using namespace std;
int a[5010];
int main()
{
	int n;
	cin>>n;
	a[1]=1,a[2]=2;//设定初始状态 
	
	for(int i=3;i<=n;i++)//递推求解 
	a[i]=a[i-1]+a[i-2];
	
	cout<//输出n级台阶的方案 
	return 0;
} 

---

优化思路（100分）：

1.当我们写出状态转移方程后，会发现其实就是斐波那契数列，这个数列是以指数趋势增长的，观察数据范围，n最大为5000，那么即使是long long 数组也无法存放这么大的数字，所以想到了高精度求解

2.创建一个二维数组，行号表示第i级台阶，列号表示方案数，下标1表示个位，下标2表示十位，以此类推，设置len为每两个数相加的最大的长度，也就是最大的列号，每次都将相同数位上的数字相加，此位保留结果的余数，下一个列号加上进位

3.因为两个相同位数的加数结果相加，和最多也是多一位，所以相加完以后判断最最大列号是否产生了值，如果产生了，则遍历的范围1-len，len++

4.最后输出数组a第n行的值，注意是倒序输出，判断前导0；

.

---

#include
using namespace std;
int a[5010][5010];
int len=1;//列号下标遍历的长度 
 
void js(int k)
{
	for(int i=1;i<=len;i++)//将k级台阶对应的方案数相加 
	{
		a[k][i]=a[k-1][i]+a[k-2][i];
	}
	
	for(int i=1;i<=len;i++)//对k行每列的数进行处理 
	{
		a[k][i+1]=a[k][i+1]+a[k][i]/10;//后一位应该加上本位的进位 
		a[k][i]=a[k][i]%10;//本位应该保留余数 
	}
	
	if(a[k][len+1]!=0)//如果相加的结果的列号多出来了 
	len++;//遍历的长度加1 
}
int main()
{
	int n;
	cin>>n;
	a[1][1]=1,a[2][1]=2;//设定初始状态 
	
	for(int i=3;i<=n;i++)//高精度求解 
	js(i); 
	
	for(int i=len;i>=1;i--)//倒序输出n行的每个数 
	cout<
	return 0;
}