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?

思考：

使用动态规划，确定当前登到第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

本文出自 “做最好的自己” 博客，请务必保留此出处http://qiaopeng688.blog.51cto.com/3572484/1844815

leetCode 70. Climbing Stairs | 动态规划