跳台阶问题扩展
跳台阶问题扩展(AC)
1、问题描述
一只青蛙一次可以跳上1级台阶,也可以跳上2级...也可以跳上n级。求该青蛙跳上一个n级的台阶(n为正整数)总共有多少种跳法。
数据范围:1\le n\le20
进阶:空间复杂度O(1),时间复杂度O(1)
示例1:
输入:
3
输出:
4
示例2:
输入:
1
输出:
1
2、解题思路
解释:f(n)表示跳到第n级台阶的方法数
f(1)=1 //直接跳到第一级台阶
f(2)=f(2-1)+f(2-2) //先到1再到2,或者直接到2
f(3)=f(3-1)+f(3-2)+f(3-3)
...
f(n-1)=f(n-2)+f(n-3)+...+f(n-1-(n-1))
f(n)=f(n-1)+f(n-2)+f(n-3)+...f(n-n)
简化下:
f(n-1)=f(n-2)+f(n-3)+...+f(1)+f(0)
f(n)=f(n-1)+f(n-2)+f(n-3)+...+f(1)+f(0)
两式相减可得:
f(n)=2f(n-1)
跳法整理如下:
f(n)=\left\{\begin{matrix}
1 &,n=1 \\
2 &, n=2\\
2*f(n-1) &,n\ge 2
\end{matrix}\right.
3、代码实现
public class Solution {
public static int jumpFloorII (int number) {
// write code here
if(number==1){
return 1;
}
if(number==2){
return 2;
}
return 2*jumpFloorII(number-1);
}
public static void main(String[] args) {
System.out.println(jumpFloorII(3));
System.out.println(jumpFloorII(1));
}
}
本文作者: 别团等shy哥发育
版权声明: https://www.codeleader.top/ 本博客所有文章除特别声明外,均采用 BY-NC-SA 许可协议。转载请注明出处!
评论
匿名评论
隐私政策
你无需删除空行,直接评论以获取最佳展示效果