题解 | #跳台阶扩展问题#
跳台阶扩展问题
http://www.nowcoder.com/practice/22243d016f6b47f2a6928b4313c85387
共有n个台阶，如果换个角度思考，每个台阶被踩到/不被踩到的概率各是1/2。由于青蛙肯定要踩到n个台阶中最上面的一个，那么对于剩下的n-1个台阶，每个台阶都有两种状态（被踩到和不被踩到），这时候考虑一组组合数C（n-1，0）(没有台阶被踩到），C(n-1,1)（1个台阶被踩到）......C(n-1,n-1)，这些值的和就是所有情况的个数，由二项式定理，最终结果应该是2^n-1
