题解 | #跳台阶扩展问题#
跳台阶扩展问题
http://www.nowcoder.com/practice/22243d016f6b47f2a6928b4313c85387
使用和跳台阶一样的思路。模拟跳的过程，将n阶台阶分为第一次跳1阶，第一次跳2阶，...，第一次跳n阶。
这样就得到了一个类似于原始跳台阶的公式，f(n)=f(1)+f(2)+...+f(n-1)+1，f(n)表示n阶台阶的跳法数。
最后不是加f(n)而是加1，是因为一次跳n个台阶就直接跳完了，只有一种跳法。如果加f(n)的话会使等式不成立，使递归无出口。这个最后加1在代码中体现为返回++sum。
由于在循环中调用递归，所以时间复杂度在O(n^2)，是比较大的，算法还有进一步优化的空间。
class Solution {
public:
int jumpFloorII(int number) {
if(number == 0){
return 0;
}
else if(number == 1){
return 1;
}
else if(number == 2){
return 2;
}
int sum = 0;
for(int i = 1;i < number;i++){
sum += jumpFloorII(i);
}
return ++sum;
}
};
