青蛙爬楼梯（LeetCode 70）C语言递归思想

目录

题目来源

函数介绍

问题示例

函数实现1

用法示例

结果展示

 函数实现2（递归思想）

跳台阶 升级版

函数介绍

问题示例

函数实现

用法示例

结果展示

---

题目来源

70. 爬楼梯 - 力扣（LeetCode） (leetcode-cn.com)https://leetcode-cn.com/problems/climbing-stairs/submissions/

函数介绍

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

问题示例

输入：n = 2
输出：2
解释：有两种方法可以爬到楼顶。
1. 1 阶 + 1 阶
2. 2 阶

输入：n = 3
输出：3
解释：有三种方法可以爬到楼顶。
1. 1 阶 + 1 阶 + 1 阶
2. 1 阶 + 2 阶
3. 2 阶 + 1 阶

函数实现1

思路：

动态规划（最优解可以从其子问题的最优解来有效地构建）
第 i 阶可以由以下两种方法得到：
在第 (i-1)阶后向上爬1阶
在第 (i-2)阶后向上爬2阶
所以到达第i阶的方法总数就是到第(i-1)阶和第(i-2)阶的方法数之和。

int climbStairs(int n) 
{
    if(n<=2)    return n;//可以舍去
    int p = 0, q = 0, r = 1;
    for (int i = 1; i <= n; ++i)
    {
        p = q;//p记录到达（i-2）阶前的方法数和
        q = r;//q记录到达（i-1）阶前的方法数和
        r = p + q;//r记录到达第i阶的方法总数 ，就是到第(i-1)阶和第(i-2)阶的方法数之和
    }
    return r;
}

用法示例

#include
int climbStairs(int n)
{
    if(n<=2)    return n;
    int p = 0, q = 0, r = 1;
    for (int i = 1; i <= n; ++i)
    {
        p = q;
        q = r;
        r = p + q;
    }
    return r;
}
int main()
{
	int n = 0;
	scanf("%d", &n);
	int count = climbStairs(n);
	printf("跳到第%d阶台阶有%d种跳法", n, count);
	return 0;
}

结果展示

 

 函数实现2（递归思想）

时间效率较低，力扣通不过的，不过也是一种思路

int climbStairs(int n)
{
	if (n == 1)
	{
		return 1;
	}
	else if (n == 2)
	{
		return 2;
	}
	else if (n > 2)
	{
		return climbStairs(n - 1) + climbStairs(n - 2);
	}
}

跳台阶 升级版 函数介绍

     一只青蛙一次可以跳上1级台阶，也可以跳上2级,它也可以跳n级，
     此时该青蛙跳上一个n级的台阶总共有多少种跳法？

问题示例

输入：n = 2
输出：2
解释：有两种方法可以爬到楼顶。
1. 1 阶 + 1 阶
2. 2 阶

输入：n = 3
输出：4
解释：有四种方法可以爬到楼顶。
1. 1 阶 + 1 阶+ 1 阶
2. 2 阶 + 1 阶
3. 1 阶 + 2 阶
4. 3 阶

函数实现

int fib(int n)
{
	if (n==1)
	{
		return 1;
	}
	else 
	{
		return 2 * fib(n - 1);
	}
	
}

用法示例

#include
int fib(int n)
{
	if (n==1)
	{
		return 1;
	}
	else 
	{
		return 2 * fib(n - 1);
	}
	
}
int main()
{
	int n=0;
	scanf_s("%d", &n);
	int count = fib(n);
	printf("跳到第%d阶台阶有%d种跳法", n, count);
	return 0;
}

结果展示