爬楼梯

题目描述：

问题分析：

1.表面上是一个动态规划的问题；
2.但经过分析实际上是一个斐波那契数列；
3.使用递归代价有点大；
4.直接加上去，避免了函数调用的代价，但是空间上要留足够的资源，所谓空间换时间，时间换空间；
5.由letcode所给出的返回类型为普通整型，所以数组的空间可以从200减少到50， 因为过了50之后，对应的值已经超过了普通整型的描述范围；

完整代码：

#include<iostream>
using namespace std;

long long int gettime(int n)
{
	long long int a[100] = {0};
	a[0] = 0,  a[1] = 1, a[2] = 2;
	
	if (n <= 2) return a[n];
	
	int i = 0;
	for (i = 3; i <= n; i++)
	{
		a[i] = a[i-1] + a[i-2];
		cout << a[i] <<endl;
	}
	
	return a[i-1];
}

//补充一个不浪费空间的例子，不过也是没考虑是否整型溢出得问题
 int climbStairs(int n) 
 {
    if (n <= 2) return n;

    int t1 = 1, t2 = 2, t3 = 0;

    for (int i = 3; i <= n; i++)
    {
        t3 = t1 + t2;
        t1 = t2;
        t2 = t3;
    }

    return t3;  
}

int main()
{
	int n;
	while (cin >> n)
	{
		long long int times = gettime(n);
		cout << n << "need :" << times << endl;
	}
	
	return 0;
}

结果展示：