题目描述 一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。
这道题借之前青蛙跳台阶的噱头，然而和动态规划一点关系都没有。是一个典型的排列组合问题 其实就是空当插隔板。 总共的选择可以用如下公式进行表示：
C0n+C1n+C2n+……+Cnn=2n
所以就很简单了。
class Solution {
public:
int jumpFloorII(
int number) {
if(number<=
2)
return number;
int cur=
2;
int next;
for(
int i=
3;i<=number;++i)
{
next=cur
*2;
cur=
next;
}
return next;
}
};
转载请注明原文地址: https://ju.6miu.com/read-4590.html
