70. Climbing Stairs

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?

思考：

top steps
1 1
2
 2
3
 3
4
 5
5
 8
6
 13
...
 ...
从上面的分析可以看出，f(top) = f(top - 1) + f(top - 2)

使用动态规划，确定当前登到第i级台阶可能的步数是几。然后在查看下一级i+1台阶的可能步数。

代码实现如下：

class Solution {public:    int climbStairs(int n)     {    	if (n <= 0)    		return 0;    	if (n <= 2)    		return n;        	int a[2] = {1,2};    	int tmp = 0;    	for (int i = 0; i < n - 2; ++i)    	{    		tmp = a[0] + a[1];    		a[0] = a[1];    		a[1] = tmp;    	}        	return tmp;    }};

总结：

先确定当前的结果，然后转移。确定下一步的结果。依次转移，直到结果。

2016-08-31 16:17:16