[C++知识库]跳台阶 (C语言)

题目：一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法（先后次序不同算不同的结果）。此题和牛客网的小乐乐走台阶是一样的

? ? ?

思路：把数组arr[i]当做台阶，i=1为第一阶，i=2为第二阶......

第三个台阶的时候可以从第一阶和第二阶直接走上来；
同理，第四个台阶的时候可以从第二阶和第三阶直接走上来；
第五个台阶的时候可以从第三阶和第四阶直接走上来；
… …

?代码如下：

//方法一：记忆化搜索
int jumpFloor(int n)
{
	if (n == 1)
		return 1;
	else if (n == 2)
		return 2;
	else
	{
		int arr[50] = {0};
		int i;
		arr[1] = 1;
		arr[2] = 2;
		
		for ( i = 3; i <=n; i++)
		{
			arr[i] = arr[i - 1] + arr[i - 2];
		}
		return arr[i-1];
	}

}

?递归的时候，让i=0也定义为1，便于递归计算

//方法二：递归
int Fibonacci(int n)
{
    if (n<=1) //这里需要把n=0情况定义
        return 1;
    return Fibonacci(n-1) + Fibonacci(n-2);
}

?