剑指Offer经典面试题：C语言实现青蛙跳台阶问题。希望大家能帮我看看错在哪儿了？

Question

#include<stdio.h>

//青蛙跳台问题

int Fac(int num)//求阶乘的函数
{
	if (num > 1)
	{
		return num * Fac(num - 1);
	}
	else
	{
		return 1;
	}
}

int main()
{
	//输入台阶个数n
	int n = 0;
	scanf("%d", &n);

	//sum为计算跳台阶情况的临时变量
	//初值设为1的原因是因为第一次选择全部跳一阶也是一种情况
	int sum = 1;
	int count1 = n;//全部跳一阶
	int count2 = 0;//记录一次跳两阶的次数

	//开始用二去一个一个地替换
	//先判断一的个数是否大于等于2，才能保证可以将两次跳一阶替换为一次跳两阶
	while (count1 >= 2)
	{
		count1 -= 2;
		count2++;
		//现在已经有了用两个一阶替换了一个二阶的情况
	//然后需要把它们进行组合，并计算所有组合的情况数
	//计算思路为：先将它们进行有序全排列，再减去重复排列的情况
	//但是需要判断count1和count2是否大于1，不大于一的话就不需要考虑重复排列的情况

	//有序全排列计算就是求（count1+count2）的阶乘
		if (count1 < 2 && count2 < 2)
		{
			sum += Fac(count1 + count2);
		}
		if (count1 >= 2 && count2 < 2)
		{
			sum += Fac(count1 + count2) - Fac(count1) + 1;//这里+1是因为要保留一种排列情况
		}
		if (count1 < 2 && count2 >= 2)
		{
			sum += Fac(count1 + count2) - Fac(count2) + 1;//这里+1是因为要保留一种排列情况
		}
		if (count1 >= 2 && count2 >= 2)
		{
			sum += Fac(count1 + count2) - Fac(count1) + 1 - Fac(count2) + 1;
		}
	}

	printf("%d\n", sum);

	return 0;
}

结果是不对的

 

Answer 1

动态规划入门题，参考公式f(n) = f(n - 1) + f(n - 2)也就是要跳到第n阶有两种可能，要么从n-2阶跳两步，要么从n-1阶跳1步，如此迭代即可；

初始化f(1) = 1，f(2) = 2；