题目描述：
一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法（先后次序不同算不同的结果）。
解题思路与代码：
1) 只有1级台阶，跳法：1；有2级台阶，跳法：2。（每次跳1级 or 一次跳2级）
class Solution {
public:
int jumpFloor(int number) {
if (number<=0) return 0;
if (number<=2) return number;
long long numJump = 2;
long long temp = 1;
for (int i = 3;i<=number;i++){
numJump = numJump + temp;
temp = numJump - temp;
}
return numJump;
}
};
2) 设共跳x个1级台阶，y个2级台阶，可推出x+2y=n => x=n-2y,最终问题为对n-2y个一级台阶与y个2级台阶排列组合，即C(n-y,y)。y的范围：y>=0&&y<=(n/2) x的范围：x>=0&&x<=n。
C(n-y,y) ：一共有数字 (n-2*y) +y = n - y 个数字(2与1)。在(n-y)个位置中挑出y个位置放2，其余位置放1。因此对每个y值计算C(n-y,y)，所有y值的和，即为解。
C(m,n)=m! / ( n!(m-n)! ) = m(m-1)(m-2)...(m-n+1) / n!
class Solution {
public:
int jumpFloor(int number) {
int count = 0;
for(int two = 0;two<= (number/2);two ++){ //two(y) 跳两级台阶的次数
count += com(number-two,two);
}
return count;
}
int com(int m,int n){ //计算C(n-y,y)
int i = m;
int sum=1;
for(int j = 0;j < n;j++,i--){
sum = sum *i / (j+1);
// m/1 (m-1)/2 (m-2)/3 ... (m-n+1)/n
}
return sum;
}
};
基础知识：
[1] 排列组合：排列问题，考虑顺序；组合问题，不考虑顺序。
考虑是否重复又可分为排列可重复问题、排列不可重复问题、组合可重复问题、组合不可重复问题。