笔试算法：青蛙跳台阶
1、题目表述
//假设青蛙正在跳台阶。需要 n 阶你能到达楼顶。
//每次青蛙可以跳 1 或 2 个台阶，但不可以连续跳2个。请问有多少种不同的方法可以到楼顶呢？
//注意：给定 n 是一个正整数。
2、解析
从题目描述中我们可以发现，每次只能跳1或2个台阶，即当我们到达楼顶前的最后一次也是跳了1或2个台阶。 用公式表示为：
f
(
x
)
=
f
(
x
−
1
)
+
f
(
x
−
2
)
f(x)=f(x-1)+f(x-2)
f(x)=f(x−1)+f(x−2)其中：f(x)表示青蛙到达x级台阶的方法数量
f(x-1)表示青蛙跳了一个台阶到达x级台阶
f(x-2)表示青蛙跳了两个台阶到达x级台阶
那么我们便可以采用递归或者动态规划的方式计算n阶台阶到达楼顶的方法数量。
3、代码
递归
int ClimbStairs(int n)
{
if (n <= 2)
return n;
return ClimbStairs(n - 1) + ClimbStairs(n - 2);
}
动态规划
int climbStairs(int n) {
if (n <= 1) return 1;
int f[n + 1];
f[0] = 1;
f[1] = 1;
f[2] = 2;
for (int i = 3; i <= n; i++)
f[i] = f[i - 1] + f[i - 3];
return f[n];
}
4、题目升级
在题目的基础上加了一个小限制，青蛙每次可以跳1或2个台阶，但是青蛙不能连续跳2个台阶，求青蛙到达n级台阶的方法数？
5、分析
不能连续跳2个台阶，也就是说如果一次跳了2个台阶，下一次只能跳1个台阶。
假设f(x)表示当前跳到了x级台阶
g(x,1)表示当前跳到了x级台阶并且上一步跳了1级台阶
g(x,2)表示当前跳到了x级台阶并且上一步跳了2级台阶
那么同理可得：
f
(
x
)
=
g
(
x
,
1
)
+
g
(
x
,
2
)
f(x)=g(x,1)+g(x,2)
f(x)=g(x,1)+g(x,2)
因为g(x-1):只跳1级台阶到x级，等价于f(x-1):x-1级台阶跳1级到x级,那么：
g
(
x
,
1
)
=
f
(
x
−
1
)
g(x,1)=f(x-1)
g(x,1)=f(x−1)
因为跳到x级跳了2个台阶，那么上一次只能跳一个台阶，那么：
g
(
x
,
2
)
=
g
(
x
−
2
,
1
)
g(x,2)=g(x-2,1)
g(x,2)=g(x−2,1)
由f(x-1)=g(x,1)得到
g
(
x
−
2
,
1
)
=
f
(
x
−
3
)
g(x-2,1)=f(x-3)
g(x−2,1)=f(x−3)
所以：
f
(
x
)
=
g
(
x
,
1
)
+
g
(
x
,
2
)
=
f
(
x
−
1
)
+
f
(
x
−
3
)
f(x)=g(x,1)+g(x,2)=f(x-1)+f(x-3)
f(x)=g(x,1)+g(x,2)=f(x−1)+f(x−3)
因此，经过以上分析，该方法也就同样归结为动态规划
6、代码
递归
int ClimbStairs(int n)
{
if (n == 0) return 1;
if (n == 2||n==1)
return n;
return ClimbStairs(n - 1) + ClimbStairs(n - 3);
}
动态规划
int ClimbStarirs(int n)
{
if (n <= 1) return 1;
vector<int> f(n+1,-1);
f[0] = 1;
f[1] = 1;
f[2] = 2;
for (int i = 3; i <= n; i++)
f[i] = f[i - 1] + f[i - 3];
return f[n];
}
7、总结
以上就是青蛙跳台阶的所有内容，涉及到十分重要的动态规划问题，也是大厂笔试的常考题，早已在完美世界、字节跳动和leetcode等的算法题中出现过类似题型，值得重视。
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
