题目:
- You are climbing a stair case. It takes n steps to reach to the top.
- Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?
- Note: Given n will be a positive integer.
- Example 1:
- Input: 2
- Output: 2
- Explanation: There are two ways to climb to the top.
- 1. 1 step + 1 step
- 2. 2 steps
- Example 2:
- Input: 3
- Output: 3
- Explanation: There are three ways to climb to the top.
- 1. 1 step + 1 step + 1 step
- 2. 1 step + 2 steps
- 3. 2 steps + 1 step
要完成的函数:
int climbStairs(int n)
说明:
其实这道题目不是让我们真的去穷举所有情况, 然后输出计数结果. 而是让我们去发现背后的数学规律, 然后输出结果就可以了. 之前笔者也想要穷举, 但是实在太复杂了. 后来参考了一下 discussion 中大神的做法, 然后推了一下, 发现了如下规律:
1, 比如 n=5 的时候, 有多少种情况, 其实是建立在 n=3 的情况下和 n=4 的情况下的. 因为爬楼梯五步不可能一气呵成, 题目规定了每次只能一步或者两步, 所有登上第五个台阶之前, 要不就是已经登了 3 个台阶, 然后再一次性跨两个台阶; 要不就是已经登了 4 个台阶, 然后再跨一个台阶. 所以 n=5 的时候有多少种情况, 其实就是 n=3 的时候的情况总数 + n=4 的时候的情况总数.
2, 有的朋友可能会觉得会不会 n=4 的情况有一些包含在 n=3 的情况里面. 其实不会的, 最后不会重叠, 因为 n=3 的时候最后再一次性跨两个台阶, n=4 的时候是只跨一个台阶. 两者的表示结果是不一样的.
3, 所以这其实是一个斐波那契数列.
PS: 关于要如何想到这个结论.
笔者自己在推 n=3,n=4,n=5 的情况的时候, 其实发现了这个推理过程有点像 viterbi 算法. 然后又觉得比如 n=5 的情况, 登上 5 个台阶的情况不是一气呵成的, 是建立在 n=3 和 n=4 的情况的基础上的. 由此应该可以推出这个结论, 膜拜 discussion 区域的大神.
代码:
- int climbStairs(int n)
- {
- if(n==1)
- return 1;
- else if(n==2)
- return 2;
- n=n-2;
- int a=1,b=2,c;
- while(n--)
- {
- c=b;
- b=a+b;
- a=c;
- }
- return b;
- }
来源: http://www.bubuko.com/infodetail-2551433.html