题目描述:一只青蛙一次可以跳上1级台阶,也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法(先后次序不同算不同的结果)
个人思路:使用时间复杂度较大的算法,如斐波那契数列可以求解,将对n阶阶梯步数问题递归为n-1阶阶梯步数和n-2阶阶梯步数之和。但其实这个问题可以转化为一个数学问题,然后编程实现这个数学方法即可。
这里使用高中知识里的排列组合方法,当有n个台阶时,青蛙可以跳二阶的次数是0到n/2。
于是,单从跳阶次数来说,可以产生n/2+1种跳法,1阶个数从n降到n%2,2阶个数从0升至n/2,总的步数从n降至n/2+n%2。
我们就用这几个数字进行计算。
从总步数角度出发,从n降至n/2+n%2的过程,从总步数里挑选2步的个数,进行排列,由于一步之间和二步之间是没有区分的,所以这里使用高中数学里的C符号,计算它的排列,然后加和,最终得到的结果即为青蛙跳阶总的跳法。
算法原理比较简单,需要注意的是边界值,防止在计算过程中遗漏特殊情况。
对这个算法的实现如下所示:
其中,target是传进去的台阶数,sum是跳法计数器,list_nums方法用来计算每一种的排列个数。
public class Solution {
public int JumpFloor(int target) {
int sum=0;
for(int i=target;i>=target/2+target%2;i--){
sum+=list_nums(i,target-i);
}
return sum;
}
public int list_nums(int a,int b){
long num=1;
for(int i=0;i<b;i++)
num*=(a-i);
for(int i=b;i>=1;i--)
num/=i;
return (int)num;
}
}
在编程练习网站上试运行,呐,成功通过本题!